最大素因子

yangchuanju

最大素因子
设m是一个正整数，
如果m是一个二合数，则它的最小素因子小于m的平方根，最大素因子大于m的平方根。

如果m是一个三合数，令它的最小素因子是p1，次小素因子是p2，最大素因子是p3，则最大素因子p3大于m/p1的平方根；
例30=2*3*5,30除以2等于15，平方根不到4，最大素因子5大于4。

如果m是一个四合数，令它的最小素因子是p1，次小素因子是p2，最大素因子是p4，则最大素因子p4大于m/[p1*p2]的平方根；
例210=2*3*5*7,210除以2*3等于35，平方根不到6，最大素因子7大于6。
……

yangchuanju

如何寻找大素数
截至目前，前几个已知的最大素数都是梅森素数2^p-1，现知道的最大素数为2^82589933-1，有24862048位；
太阳先生一直想找一个大于等于1亿位的大素数，若它是梅森素数则它的指数一定是大于3亿的素数。

1亿位梅森素数不易找到，1亿位梅森数的余因子恐怕更难找到。
某个梅森数若是一个二合数，则它的最大素数大于梅森数的平方根，指数9亿的二合数梅森数的最大素因子应该达到1亿位；
设梅森数中的梅森素数分率是s，则二合数的分率也不比梅森素数分率大多少，仍为s上下，况且判断这个余因子的难度要比判断一个梅森数是不是素数更难。
多因子梅森数的最大素因子有多大，无法估计。

2^2p-1、4^3p-1都不是素数，2^2p-1=(2^p+1)*(2^p-1)、4^3p-1=(2^3p+1)*(2^3p-1)=(2^p+1)*(2^2p-2^p+1)*(2^p-1)*(2^2p+2^p+1)，
想在2^p+1、2^2p-2^p+1、2^2p+2^p+1之中寻找大素数（最大素因子）又会怎么样？
虽然它们中间都含有大素数因子，但你有如何确定它们是素数呢？

yangchuanju

太阳命题：
已知：2^k-1>m,  m是(4^3k-1)/[(2^3k-1)*(2^k+1)]的最大质因子
t是(4^3k-1)/[(2^3k+1)*(2^k-1)]的最大质因子，素数k>0
求证：t>2^k-1；m>2^k-1

4^3k-1=(2^3k-1)*(2^3k+1)；
2^3k-1=(2^k-1)*(2^2k+2^k+1)；
2^3k+1=(2^k+1)*(2^2k-2^k+1)；
(4^3k-1)/[(2^3k-1)*(2^k+1)]=2^2k-2^k+1，m是2^2k-2^k+1的最大素因子；
(4^3k-1)/[(2^3k+1)*(2^k-1)]=2^2k+2^k+1，t是2^2k+2^k+1的最大素因子。

t是2^2k+2^k+1的最大质因子，
如果2^2k+2^k+1是一个二合数，则t大于2^2k+2^k+1的平方根。
假定2^2k+2^k+1的平方根>2^k-1，
平方2^2k+2^k+1>2^2k-2*2^k+1
3*2^k>0始终成立，假定正确；从而得到t>2^k-1。

m是2^2k-2^k+1的最大质因子，
如果2^2k-2^k+1是一个二合数，则m大于2^2k-2^k+1的平方根。
假定2^2k-2^k+1的平方根>2^k-1，
平方2^2k-2^k+1>2^2k-2*2^k+1
2^k>0始终成立，假定正确；从而得到m>2^k-1。

如果2^2k±2^k+1是一个多因子合数，则t、m是否大于2^k-1无法轻易断定。

太阳

太阳

t是(4^1563-1)/(2^1563+1)/(2^521-1)最大的质因数
t＝1002877602096860912994658135411150252730605177753954452446360142457390598541985147896218302589806484168961463859067500637863331674650844683467971031496519
2^521-1＞1002877602096860912994658135411150252730605177753954452446360142457390598541985147896218302589806484168961463859067500637863331674650844683467971031496519
结论：(4^1563-1)/(2^1563-1)/(2^521+1)最大质因数大于(2^521-1)
(4^1563-1)/(2^1563-1)/(2^521+1)/c＝d，使用试除法，c取大数试除，( c＞2^521-1)，可以整除，c必定是素数
这样提快速度找到大素数

太阳

不知道4楼命题是否正确？还没有找到反例

太阳

否定这个命题，证明此命题是错误的，那是相当难，
证明\(\left( 4^{3k}-1\right)的最大质因数小于\sqrt[6]{4^{3k}-1}\)，基本上可以否定此命题

太阳

我们看一个特殊例子
k＝59，4^177-1＝3^2 · 7 · 2833 · 13099 · 37171 · 179951 · 184081 · 1824726041<10> · 27989941729<11> · 3203431780337<13> · 4453762543897<13> · 1898685496465999273<19> · 9213624084535989031<19>
当m＞2^59-1，此命题仍然是成立，还是没有被否定，(m＞2^59-1，违背本命题题条件，啥去)
\(\left( 4^{177}-1\right)\)的最大质因数是9213624084535989031
9213624084535989031＞\(\sqrt[6]{4^{177}-1}\)，无法否定此命题

太阳

1亿大素数：如何去找？借助第51个梅森素数\(2^{82589933}-1\)
\(\left( 4^{247756799}-1\right)\)的最大质因数大于10亿位
必定有\(4^{247756799}-1的最大质因数＞2^{82589933}-1\)

yangchuanju

太阳 发表于 2023-4-29 20:16
t是(4^1563-1)/(2^1563+1)/(2^521-1)最大的质因数
t＝1002877602096860912994658135411150252730605177753 ...

2^521-1<157>=6864797660...51<157>素数
2^1563-1<471>=
7*67939363836931489207<20>*116824145827723574519813228479<30>*370703114574830523729359630482697673598177<42>*2281545765...09<70>*1002877602...19<154>*6864797660...51<157>
2^521+1<157>=
3*501203*443418473521<12>*90268296000189649868678102552775904610963<41>*1140627393...79<99>
2^1563+1<471>=
3^2*501203*128678814049<12>*443418473521<12>*30006632620851811<17>*90268296000189649868678102552775904610963<41>*1140627393...79<99>*4068271388...09<286>合数
4^521-1<314>=
3*501203*443418473521<12>*90268296000189649868678102552775904610963<41>*1140627393...79<99>*6864797660...51<157>
4^1563-1<942>=
3^2*7*501203*128678814049<12>*443418473521<12>*30006632620851811<17>*67939363836931489207<20>*116824145827723574519813228479<30>*90268296000189649868678102552775904610963<41>*370703114574830523729359630482697673598177<42>*2281545765...09<70>*1140627393...79<99>*1002877602...19<154>*6864797660...51<157>*4068271388...09<286>合数

4^1563-1=(2^1563-1)*(2^1563+1)=(2^521-1)*(2^1042+2^521+1)*(2^521+1)*(2^1042-2^521+1)
已知2^521-1是一个梅森素数，从2^1563-1中去掉2^521-1可得2^1042+2^521+1=
7*67939363836931489207<20>*116824145827723574519813228479<30>*370703114574830523729359630482697673598177<42>*2281545765...09<70>*1002877602...19<154>
最大素因子1002877602...19<154>小于2^521-1<157>=6864797660...51<157>素数

2^1042-2^521+1=(2^1563+1<471>)/(2^521+1)=
3*128678814049<12>*30006632620851811<17>*4068271388...09<286>
2^1042-2^521+1（源于2^1563+1）之中有一个尚未完全分解的286位的复合因子，它又含有什么素因子呢？
这个286位的复合因子的小素因子一定大于99位，另一因子就不大于187位，但要大于143位（平方根位数）；
最大素因子143-187位，只能说有可能大于157位的2^521-1。