 mersenneforum.org Ten Billion Digits Mersenne Numbers
 Register FAQ Search Today's Posts Mark Forums Read  2012-05-10, 20:38 #1 aketilander   "Åke Tilander" Apr 2011 Sandviken, Sweden 2×283 Posts Ten Billion Digits Mersenne Numbers Well, I got a bit carried away and trial factored the smallest 100 Ten Billion Digits Mersenne Numbers with prime exponents (M33,219,280,951 - M33,219,283,529) up till ^70 bits and found 62 factors Here is the result: Code: M33219280951 has 0 factors in [2^1, 2^70-1]. M33219281003 has a factor: 61455669855551 - Program: L5.0x M33219281003 has 1 factors in [2^1, 2^70-1]. M33219281023 has 0 factors in [2^1, 2^70-1]. M33219281027 has 0 factors in [2^1, 2^70-1]. M33219281063 has 0 factors in [2^1, 2^70-1]. M33219281111 has a factor: 2391788239993 - Program: L5.0x M33219281111 has a factor: 294465063646236102041 - Program: L5.0x M33219281111 has a factor: 6976049033311 - Program: L5.0x M33219281111 has 3 factors in [2^1, 2^70-1]. M33219281159 has a factor: 66438562319 - Program: L5.0x M33219281159 has 1 factors in [2^1, 2^70-1]. M33219281201 has 0 factors in [2^1, 2^70-1]. M33219281213 has 0 factors in [2^1, 2^70-1]. M33219281243 has 0 factors in [2^1, 2^70-1]. M33219281267 has 0 factors in [2^1, 2^70-1]. M33219281269 has a factor: 797262750457 - Program: L5.0x M33219281269 has 1 factors in [2^1, 2^70-1]. M33219281279 has a factor: 66438562559 - Program: L5.0x M33219281279 has 1 factors in [2^1, 2^70-1]. M33219281297 has 0 factors in [2^1, 2^70-1]. M33219281299 has 0 factors in [2^1, 2^70-1]. M33219281327 has 0 factors in [2^1, 2^70-1]. M33219281371 has a factor: 16894663979942936777 - Program: L5.0x M33219281371 has 1 factors in [2^1, 2^70-1]. M33219281383 has 0 factors in [2^1, 2^70-1]. M33219281393 has a factor: 234042327863488769 - Program: L5.0x M33219281393 has a factor: 150788962099105601 - Program: L5.0x M33219281393 has 2 factors in [2^1, 2^70-1]. M33219281399 has a factor: 1594525507153 - Program: L5.0x M33219281399 has a factor: 34880245468951 - Program: L5.0x M33219281399 has 2 factors in [2^1, 2^70-1]. M33219281411 has 0 factors in [2^1, 2^70-1]. M33219281437 has a factor: 492321512315809895599 - Program: L5.0x M33219281437 has 1 factors in [2^1, 2^70-1]. M33219281441 has 0 factors in [2^1, 2^70-1]. M33219281449 has a factor: 730824191879 - Program: L5.0x M33219281449 has 1 factors in [2^1, 2^70-1]. M33219281453 has a factor: 5919675954924601 - Program: L5.0x M33219281453 has 1 factors in [2^1, 2^70-1]. M33219281467 has 0 factors in [2^1, 2^70-1]. M33219281479 has 0 factors in [2^1, 2^70-1]. M33219281489 has a factor: 116996795601600546271 - Program: L5.0x M33219281489 has 1 factors in [2^1, 2^70-1]. M33219281497 has a factor: 80462680625025497 - Program: L5.0x M33219281497 has 1 factors in [2^1, 2^70-1]. M33219281507 has 0 factors in [2^1, 2^70-1]. M33219281521 has a factor: 16476763634417 - Program: L5.0x M33219281521 has a factor: 689012466796645582273 - Program: L5.0x M33219281521 has 2 factors in [2^1, 2^70-1]. M33219281531 has 0 factors in [2^1, 2^70-1]. M33219281549 has a factor: 486304386450814108031 - Program: L5.0x M33219281549 has 1 factors in [2^1, 2^70-1]. M33219281569 has 0 factors in [2^1, 2^70-1]. M33219281587 has a factor: 20728831710289 - Program: L5.0x M33219281587 has 1 factors in [2^1, 2^70-1]. M33219281629 has 0 factors in [2^1, 2^70-1]. M33219281653 has a factor: 8629771426379647 - Program: L5.0x M33219281653 has 1 factors in [2^1, 2^70-1]. M33219281677 has 0 factors in [2^1, 2^70-1]. M33219281687 has 0 factors in [2^1, 2^70-1]. M33219281713 has 0 factors in [2^1, 2^70-1]. M33219281737 has a factor: 531508507793 - Program: L5.0x M33219281737 has 1 factors in [2^1, 2^70-1]. M33219281741 has a factor: 7972627617841 - Program: L5.0x M33219281741 has 1 factors in [2^1, 2^70-1]. M33219281863 has a factor: 3986313823561 - Program: L5.0x M33219281863 has 1 factors in [2^1, 2^70-1]. M33219281917 has a factor: 54940373784068791 - Program: L5.0x M33219281917 has a factor: 6909610638737 - Program: L5.0x M33219281917 has 2 factors in [2^1, 2^70-1]. M33219281933 has a factor: 797262766393 - Program: L5.0x M33219281933 has a factor: 7175364897529 - Program: L5.0x M33219281933 has 2 factors in [2^1, 2^70-1]. M33219281957 has 0 factors in [2^1, 2^70-1]. M33219282001 has 0 factors in [2^1, 2^70-1]. M33219282013 has 0 factors in [2^1, 2^70-1]. M33219282059 has a factor: 18602797953041 - Program: L5.0x M33219282059 has a factor: 4392386350969217 - Program: L5.0x M33219282059 has 2 factors in [2^1, 2^70-1]. M33219282067 has 0 factors in [2^1, 2^70-1]. M33219282079 has a factor: 12035375927452699417 - Program: L5.0x M33219282079 has 1 factors in [2^1, 2^70-1]. M33219282097 has 0 factors in [2^1, 2^70-1]. M33219282101 has a factor: 36076140361687 - Program: L5.0x M33219282101 has 1 factors in [2^1, 2^70-1]. M33219282121 has a factor: 731938037166137002199 - Program: L5.0x M33219282121 has 1 factors in [2^1, 2^70-1]. M33219282137 has 0 factors in [2^1, 2^70-1]. M33219282143 has a factor: 5479771195752336793 - Program: L5.0x M33219282143 has 1 factors in [2^1, 2^70-1]. M33219282203 has a factor: 470385035994481 - Program: L5.0x M33219282203 has a factor: 42938659516231027201 - Program: L5.0x M33219282203 has 2 factors in [2^1, 2^70-1]. M33219282211 has 0 factors in [2^1, 2^70-1]. M33219282241 has 0 factors in [2^1, 2^70-1]. M33219282287 has a factor: 151937821815764009 - Program: L5.0x M33219282287 has 1 factors in [2^1, 2^70-1]. M33219282409 has 0 factors in [2^1, 2^70-1]. M33219282451 has a factor: 92473513137322231 - Program: L5.0x M33219282451 has 1 factors in [2^1, 2^70-1]. M33219282493 has a factor: 829153291025281 - Program: L5.0x M33219282493 has 1 factors in [2^1, 2^70-1]. M33219282521 has 0 factors in [2^1, 2^70-1]. M33219282541 has 0 factors in [2^1, 2^70-1]. M33219282589 has 0 factors in [2^1, 2^70-1]. M33219282617 has 0 factors in [2^1, 2^70-1]. M33219282623 has a factor: 16742518441993 - Program: L5.0x M33219282623 has a factor: 2458226914103 - Program: L5.0x M33219282623 has 2 factors in [2^1, 2^70-1]. M33219282631 has 0 factors in [2^1, 2^70-1]. M33219282661 has a factor: 921569339581463 - Program: L5.0x M33219282661 has 1 factors in [2^1, 2^70-1]. M33219282721 has a factor: 178586863908097 - Program: L5.0x M33219282721 has 1 factors in [2^1, 2^70-1]. M33219282727 has a factor: 4489735680203452409 - Program: L5.0x M33219282727 has 1 factors in [2^1, 2^70-1]. M33219282773 has 0 factors in [2^1, 2^70-1]. M33219282779 has 0 factors in [2^1, 2^70-1]. M33219282781 has 0 factors in [2^1, 2^70-1]. M33219282821 has a factor: 79104679550253449 - Program: L5.0x M33219282821 has 1 factors in [2^1, 2^70-1]. M33219282847 has 0 factors in [2^1, 2^70-1]. M33219282869 has 0 factors in [2^1, 2^70-1]. M33219282883 has 0 factors in [2^1, 2^70-1]. M33219282907 has a factor: 797262789769 - Program: L5.0x M33219282907 has 1 factors in [2^1, 2^70-1]. M33219282923 has a factor: 797262790153 - Program: L5.0x M33219282923 has 1 factors in [2^1, 2^70-1]. M33219282937 has 0 factors in [2^1, 2^70-1]. M33219282953 has a factor: 797262790873 - Program: L5.0x M33219282953 has 1 factors in [2^1, 2^70-1]. M33219282979 has 0 factors in [2^1, 2^70-1]. M33219283039 has a factor: 20320368312088457 - Program: L5.0x M33219283039 has 1 factors in [2^1, 2^70-1]. M33219283063 has 0 factors in [2^1, 2^70-1]. M33219283133 has a factor: 44791286850946817 - Program: L5.0x M33219283133 has 1 factors in [2^1, 2^70-1]. M33219283147 has a factor: 1044414262141681 - Program: L5.0x M33219283147 has 1 factors in [2^1, 2^70-1]. M33219283151 has 0 factors in [2^1, 2^70-1]. M33219283183 has a factor: 794416900401712391 - Program: L5.0x M33219283183 has a factor: 1582367335139023 - Program: L5.0x M33219283183 has 2 factors in [2^1, 2^70-1]. M33219283217 has a factor: 41658849605921823383 - Program: L5.0x M33219283217 has 1 factors in [2^1, 2^70-1]. M33219283301 has a factor: 103297620335723969 - Program: L5.0x M33219283301 has 1 factors in [2^1, 2^70-1]. M33219283319 has 0 factors in [2^1, 2^70-1]. M33219283337 has a factor: 142251814421401423 - Program: L5.0x M33219283337 has 1 factors in [2^1, 2^70-1]. M33219283351 has a factor: 20662659998588809 - Program: L5.0x M33219283351 has 1 factors in [2^1, 2^70-1]. M33219283369 has 0 factors in [2^1, 2^70-1]. M33219283373 has a factor: 25682691677033999 - Program: L5.0x M33219283373 has 1 factors in [2^1, 2^70-1]. M33219283429 has a factor: 114459561135898990799 - Program: L5.0x M33219283429 has 1 factors in [2^1, 2^70-1]. M33219283519 has a factor: 1328771340761 - Program: L5.0x M33219283519 has 1 factors in [2^1, 2^70-1]. M33219283529 has a factor: 35725346278427761 - Program: L5.0x M33219283529 has 1 factors in [2^1, 2^70-1].   2012-05-10, 22:42 #2 Batalov   "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100011011110002 Posts Why stop there? We should start testing trillion-digit numbers already. Code: M3321928096379 has a factor 6643856192759 M3321928097483 has a factor 6643856194967 M3321928097759 has a factor 6643856195519 M3321928098803 has a factor 6643856197607 M3321928100303 has a factor 6643856200607 M3321928102019 has a factor 6643856204039 M3321928104431 has a factor 6643856208863 M3321928132499 has a factor 664385626499801 M3321928147817 has a factor 664385629563401 M3321928390169 has a factor 664385678033801 M3321928439759 has a factor 664385687951801 M3321928556909 has a factor 664385711381801 M3321928559699 has a factor 664385711939801 M3321928570811 has a factor 664385714162201 M3321928639961 has a factor 664385727992201 M3321928651313 has a factor 664385730262601 M3321928799261 has a factor 664385759852201 M3321928836311 has a factor 664385767262201 M3321929068193 has a factor 664385813638601 M3321928164167 has a factor 3986313797000401 M3321928736839 has a factor 3986314484206801 M3321929056309 has a factor 3986314867570801 M3321928125443 has a factor 737016261623285753 M3321928177429 has a factor 4080603422302944737   2012-05-11, 00:47 #3 wblipp   "William" May 2003 New Haven 1001001101102 Posts Let me know the web pages for these and I'll add a link to the them.   2012-05-11, 02:53 #4 NBtarheel_33   "Nathan" Jul 2008 Maryland, USA 5×223 Posts The question now, of course, is whether the EFF prizes are paid cumulatively, if a prime happens to be found that is both 100M and 1B digits in size. And would they institute higher prizes for higher orders of magnitude of digits. Hmm....   2012-05-11, 03:10   #5
axn

Jun 2003

13·359 Posts Quote:
 Originally Posted by NBtarheel_33 The question now, of course, is whether the EFF prizes are paid cumulatively
No, they're not. HTH.    2012-05-11, 04:29 #6 LaurV Romulan Interpreter   Jun 2011 Thailand 5·11·157 Posts Cute, haha, but what's the point? I am sure Serge's post was a joke, as he usually does (see his algorithm with adding 13). Here is a single line in pari: Code: (10:25:19) gp > p=nextprime(10^20*log(10)/log(2)); cnt=0; while(1,if(p%4==3&&isprime(q=2*p+1),print("M"p" has a factor "q);cnt++);p=nextprime(p++)) M332192809488736240559 has a factor 664385618977472481119 M332192809488736242551 has a factor 664385618977472485103 M332192809488736243919 has a factor 664385618977472487839 M332192809488736247123 has a factor 664385618977472494247 M332192809488736248023 has a factor 664385618977472496047 M332192809488736261391 has a factor 664385618977472522783 M332192809488736261991 has a factor 664385618977472523983 M332192809488736267871 has a factor 664385618977472535743 <...> <...> M332192809488737637371 has a factor 664385618977475274743 M332192809488737640659 has a factor 664385618977475281319 M332192809488737642603 has a factor 664385618977475285207 M332192809488737648999 has a factor 664385618977475297999 M332192809488737649143 has a factor 664385618977475298287 <...> *** at top-level: ...cnt=0;while(1,if(p%4==3&&isprime(q=2*p+1),pri *** ^-------------------- *** isprime: user interrupt after 5,297 ms. *** Break loop: type to continue; 'break' to go back to GP break> cnt 814 break>^C (10:25:27) gp > or if you have a very simple TF routine, done long time ago, as I have (one of the first things I ever did in pari ) (the second parameter is starting k, the third is ending k, in 2*k*p+1) Code: (10:33:32) gp > \r tf (10:33:34) gp > p=nextprime(10^20*log(10)/log(2)); while(1, printf("%d: ",p); tf(p,0,10^6,0); p=nextprime(p++)) 332192809488736234933: Factor not found, try higher start/stop values. 332192809488736234949: Factor not found, try higher start/stop values. 332192809488736234993: Factor not found, try higher start/stop values. 332192809488736235033: Factor found: 2^332192809488736235033-1 is divisible by 1979869144552867960796681 <...> <...> 332192809488736235227: Factor found: 2^332192809488736235227-1 is divisible by 118006180485921727784628119 332192809488736235309: Factor found: 2^332192809488736235309-1 is divisible by 2657542475909889882473 332192809488736235513: Factor found: 2^332192809488736235513-1 is divisible by 1993156856932417413079 332192809488736235779: Factor found: 2^332192809488736235779-1 is divisible by 725509095923399938941337 332192809488736235981: Factor found: 2^332192809488736235981-1 is divisible by 239178822831890089906321 332192809488736236499: Factor found: 2^332192809488736236499-1 is divisible by 3774374701411021119101639 332192809488736236983: Factor found: 2^332192809488736236983-1 is divisible by 725509095923399941570873 332192809488736237123: Factor found: 2^332192809488736237123-1 is divisible by 13287712379549449484921 332192809488736237339: Factor found: 2^332192809488736237339-1 is divisible by 79726274277296696961361 332192809488736237793: Factor found: 2^332192809488736237793-1 is divisible by 7972627427729669707033 332192809488736238023: Factor found: 2^332192809488736238023-1 is divisible by 183370430837782403388697 332192809488736238521: Factor found: 2^332192809488736238521-1 is divisible by 1993156856932417431127 332192809488736238593: Factor found: 2^332192809488736238593-1 is divisible by 940105650853123555218191 332192809488736238767: Factor found: 2^332192809488736238767-1 is divisible by 39863137138648348652041 332192809488736238953: Factor found: 2^332192809488736238953-1 is divisible by 7308241808752197256967 332192809488736238989: Factor found: 2^332192809488736238989-1 is divisible by 432515037954334583163679 So, what is the point? We can "generate" this "small factors" (i.e. with small k) in milliseconds, in ANY quantity we want, millions of them. But there is no use and no value in it. The amount of exponents left behind is millions of millions of millions, and we would not be able to LL even ONE of them in the next few hundred years... And if we ever will be able to LL any of them, then with such a powerful computer/system, who would care about such factors those systems could produce in picoseconds? Last fiddled with by LaurV on 2012-05-11 at 04:41   2012-05-11, 06:19   #7
aketilander

"Åke Tilander"
Apr 2011
Sandviken, Sweden

2×283 Posts Quote:
 Originally Posted by LaurV Cute, haha, but what's the point? I am sure Serge's post was a joke, as he usually does (see his algorithm with adding 13).
No I don't think there is a point. I was as I said "a bit carried away", but since you asked the question I was starting to think about it and thinking more about it its a very good question. Formulated in a different way: "Could there be a point ...?"

Well maybe. Generally speaking it could have some value to know that the distribution of factors are as expected even very high up among the Mersenne numbers. Some things about the Mersenne numbers/primes are just taken for granted but there is no mathematical proof of it, so at least it could be good to have empirical proofs. If I remember it rightly (I am on the run just now so I don't have the time to make a proper check) there is not even a mathematical proof of wether there are infinitely many composite (prime exponent) Mersenne numbers or not? All of us take this for granted, but showing that there are composites high up confirms this at least up to that limit.

So thinking more about it I really think there is a good point in having sets of Mersenne numbers trail factored way up which could be studied more closely.

But that wasn't really why I did it. It was more because it was nice doing it and nice finding a bunch of factors like that and after all Operation Billion Digits is a whimsical project. Quote:
 Originally Posted by wblipp Let me know the web pages for these and I'll add a link to the them.
There is no webpage, sorry.

And I have googled all 62 factors without finding any of them on the internet.

They are not included in Will Edgington's list here: http://www.garlic.com/~wedgingt/resu...k.split.aw.bz2

And they did not appear neither on PrimeNet nor on Mersenne aries since they don't cover these ranges.
I have submitted them to Mersenne aries now and you can find them under the largest exponent covered by the database here:
http://mersenne-aries.sili.net/expon...61455669855551

And I have, of course, searched this forum as well without finding any mention of them before.

So to the best of my knowledge they were not known before.

Last fiddled with by aketilander on 2012-05-11 at 06:47   2012-05-11, 08:54 #8 ET_ Banned   "Luigi" Aug 2002 Team Italia 2·3·13·61 Posts I think Will Edgington may enjoy them... Luigi   2012-08-20, 20:29   #9
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

2·5·293 Posts Quote:
 Originally Posted by LaurV Here is a single line in pari So, what is the point? We can "generate" this "small factors" (i.e. with small k) in milliseconds, in ANY quantity we want, millions of them. But there is no use and no value in it.
Not entirely true; I found your 1-line program very useful since I wanted to fill in the known-factor list quickly on http://mersenne-aries.sili.net for the beyond-PrimeNet M(109)-M(232) range. I had already generated about 10000 factors with k<10 in a far more inefficient manner; your PARI code was much much much faster, so I'm taking it up a bit.

Quote:
 Originally Posted by aketilander I have submitted them to Mersenne aries now and you can find them under the largest exponent covered by the database here: http://mersenne-aries.sili.net/expon...61455669855551
I probably rearranged stuff and broke your link, sorry. The factor you linked to is for an exponent 10x larger than what's currently supported on Mersenne-aries: it currently supports only prime Mersenne exponents up to M(232).

Incidentally, I now generate a daily exponent status report in the same format at PrimeNet, but for M(109)-M(232):
mersenne-aries.sili.net/primenet_gimps_summary_1G/
PM or email me if you have any interest in doing broad TF pre-factoring in this range.   2012-08-21, 02:45   #10
ixfd64
Bemusing Prompter

"Danny"
Dec 2002
California

29·79 Posts A factor I found several years ago:

Quote:
 M404253979041338401 has a factor: 4272353326450636394907689   2012-08-21, 04:45   #11
LaurV
Romulan Interpreter

Jun 2011
Thailand

21BB16 Posts Quote:
 Originally Posted by James Heinrich I found your 1-line program very useful since I wanted to fill in the known-factor list quickly . your PARI code was much much much faster, so I'm taking it up a bit.
Thanks. Why you didn't say something (here or PM)?. I played with this "elementary" things since ages and I have much faster (optimized, well, as much as pari can do) routines for eliminating small factors, and also I have files with ALL factors for Mp with p<10 billions (ten times the range of GIMPS, includes the 3.x billions of the OBD range) for up to 49 bits or so, many megabytes and few months of work. Here for example is a routine to eliminate the SG primes wich are 3 mod 4 (their correspondent mersenne are all composite, as discussed below in the thread, I think I posted variations of this many times).

Code:
elimSGp3m4(start,stop,file,pflag)=
{
my(p,d,cnt);
p=max(start,5);
cnt=0;
while(p<stop,
until(p%4==3 && isprime(d=2*p+1),
p=nextprime(p+1)
);
if(p<stop,
if(bitand(pflag,1), printf("...%d...%c",p,13));
if(bitand(pflag,2), print("M"p" is divisible by "d));
if(bitand(pflag,4), write(file,p,",",d));
cnt++
)
);
return(cnt)
};
"file" is the output, pflag is to print them on screen or not. Later on you can use a perl script to eliminate those in "file" from the prime candidate list.

Here is some TF variation, which can be used to eliminate very fast exponents with small k, up to 2^30 or so. About half of them will be gone with this "filtering". There is also a function called "ratf" (random tf) which does the same but looking for k first. Ratfpro is its "pro" version which splits the output file in different files according with bit level and exponent size. For this ratfpro, you can create a file called "flags.txt" to "gracefully shut it down", you create that file and put a single line in it, containing a "0" (ascii char code 48, then end of line). When you want your program to stop, edit the file and put a "1" and it will stop after the next save checkpoint, so you can resume next time without losing candidates (no gaps).

Code:
ten=log(10);
two=log(2);

/* p= exponent, start/stop=values of k in 8*k*p+{s*p}+1 */
tf(p,start,stop,fisout)=
{
if(p<3 || !isprime(p),print("p has to be an odd prime"); return(0));

if(p<11,print("2^"p"-1 is prime!"); return(2));

gettime();
/*m=1<<p-1;*/
if(stop==0, error("No Stop"));/*stop=sqrtint(m)\(8*p)+1);*/
sp0=2*(4-p%4)*p;
sp1=8*p-sp0;
k=start;
if(k==0,d=sp0+1;t=1,d=8*k*p+1;t=0);

/*    while(k<=stop && (n=m%d) /* faster than exponentiation n=(lift(Mod(2,d)^p)-1)*/
while(k<=stop && (n=lift(Mod(2,d)^p)-1) !=0,
if(t==0, d+=sp0, d+=sp1; k+=t);
t=1-t;
if(bitand(k,1048575)==0 && t==0,
printf("... %d bMit (k: %d) -- last tested: %d, %d digits (2^%d++), %11.6f ms/iter ...%c",
k>>20,k,d,ceil(log(d)/ten),floor(log(d)/two),gettime()/1048576.0,13);
if(fisout<>0, write(fisout,k-1))
)
);

if(n==0,
/*        print("Factor found: 2^"p"-1 = "m" is divisible by "d); return(1), */
print("Factor found: 2^"p"-1 is divisible by "d); return(1),
/*else*/
/*        if(stop>=sqrtint(m)\(8*p)+1,
print("2^"p"-1 = "m" is prime!"); return(2),
/*else*/
/*        )*/
);
}

/* get the k in 8*k*p+{s*p}+1 (negativ for s!=0. else positiv)  */
getk(d,p)=
{
if(Mod(2,d)^p!=Mod(1,d),print("Not a factor!");return);

if((a=((d-1)/p))%8==0,return(a/8),return(-(a-2*(4-p%4))/8));
}

/*get smallest p such as n divides 2^p-1*/
getp(n,limt)=
{
if(n<3 || n%2==0, print("Only odd positive numbers!");return);

rg=1;
sm=0;
until(rg==1 || sm>=limt,
rg+=n;
while(rg%2==0 && sm<limt,
rg>>=1;
sm++;
if(bitand(sm,1048575)==0, print(sm));
)
);
return(sm);
}

/*getp for a prime n (in this case p is a divisor of n-1*/
getpfp(n)=
{
my(c);
c=divisors(n-1);
for(i=1,#c,
if(c[i]<1000000000 && Mod(2,n)^c[i]==1, return(c[i]))
);
return(0);
}

/* "random" trial factoring, specify a starting possible factor and the outfput file */
ratf(a,fis)=
{
if(fis==0, print("Specify an output file!"); return(0));
while(1,
until(a%8==1 || a%8==7,a=nextprime(a+1));
c=factorint(a-1)[,1]~;
for(i=1,#c,
if(c[i]<1000000000 && Mod(2,a)^c[i]==1, print(a","c[i]); write(fis,a","c[i]))
)
);
}

/*same as above, but split the output to different files depending on n and k
-if a=-1, it will read the last_k from the file, assuming the file has ONE LINE only
-use the flags.txt file to gracefully stop it
*/
ratfpro(a,printstep)=
{
my(tnextpr,tmod,tfactint,telse);
print("Starting/continuing from: "a);
tnextpr=tfactint=tmod=telse=0;
if(printstep==0,printstep=2^20);
prst=a;
gettime();
while(1,
telse+=gettime();
until(a%8==1 || a%8==7,a=nextprime(a+1));
tnextpr+=gettime();
if(a>prst,
prst=a+printstep;
printf("... %d, (%d digits, 2^%d++) --- Timers:  %6.4f,  %6.4f,  %6.4f,  %6.4f  (seconds)\n",
a,ceil(log(a)/ten),floor(log(a)/two),
tnextpr/1000, tfactint/1000, tmod/1000, telse/1000);
extern("del fact_last_k.bak");
extern("ren fact_last_k.txt fact_last_k.bak");
write("fact_last_k.txt",a-1);
if(shouldstop==1,break)
);
telse+=gettime();
c=factorint((a-1)>>1)[,1]~;
tfactint+=gettime();
for(i=1,#c,
if(c[i]<10000000000,
telse+=gettime();
if(Mod(2,a)^c[i]==1,
tmod+=gettime();
print(a","c[i]"  ");
if(c[i]<1000000000,fis="fact_0B_",
if(c[i]<2000000000,fis="fact_1B_",
if(c[i]<3000000000,fis="fact_2B_",
if(c[i]<4000000000,fis="fact_3B_",
if(c[i]<5000000000,fis="fact_4B_",
if(c[i]<6000000000,fis="fact_5B_",
if(c[i]<7000000000,fis="fact_6B_",
if(c[i]<8000000000,fis="fact_7B_",
if(c[i]<9000000000,fis="fact_8B_",
fis="fact_9B_";
break)))))))));
expo=40;
k=1<<expo;
for(j=1,40,
if(a<k,fis=concat(fis,expo); break,
k<<=1; expo++));
write(fis,a","c[i]),
/*else*/
tmod+=gettime()
),
/*else*/
break
)
)
);
}

/*same as above, but use modular order instead of factoring k-1*/
/*for bigger stuff it may become faster than factoring k-1*/
ratfzno(a,printstep)=
{
my(tnextpr,tprchk,tznord,telse);
tnextpr=tznord=tprchk=telse=0;
gettime();
if(printstep==0,printstep=2^20);
prst=a;
while(1,
until(a%8==1 || a%8==7,a=nextprime(a+1));
tnextpr+=gettime();
if(a>prst,
prst=a+printstep;
printf("... %d, (%d digits, 2^%d++) --- Timers: %10.4f, %10.4f, %10.4f, %10.4f seconds\n",
a,ceil(log(a)/ten),floor(log(a)/two),
tnextpr/1000, tznord/1000, tprchk/1000, telse/1000);
write("fact_last_k",a));
telse+=gettime();
c=znorder(Mod(2,a));
tznord+=gettime();
if(isprime(c),
tprchk+=gettime();
if(c<1000000000,fis="fact_0B_",
if(c<2000000000,fis="fact_1B_",
if(c<3000000000,fis="fact_2B_",
if(c<4000000000,fis="fact_3B_",
if(c<5000000000,fis="fact_4B_",
if(c<6000000000,fis="fact_5B_",
if(c<7000000000,fis="fact_6B_",
if(c<8000000000,fis="fact_7B_",
if(c<9000000000,fis="fact_8B_",
if(c<10000000000,fis="fact_9B_",
telse+=gettime();
next))))))))));
expo=40;
k=1<<expo;
for(j=1,40,
if(a<k,fis=concat(fis,expo); break,
k<<=1; expo++));
print(a","c"  ");
write(fis,a","c);
telse+=gettime()
);
tprchk+=gettime()
);
}

/* it will look for prime factors of the form 2*pr(v)+1
v can include 2, p and other odd primes (or else)

call sample (copy/paste):
> p=23; xx=[0,0,0]; while((xx=pptf([2,p],xx,xx+10^4,10^6,0,0))!=p,); xx

immediate subsequent calls (to find other small factors):
> xx=%; while((xx=pptf([2,p],xx,xx+10^4,10^6,0,0))!=p,); xx

*/
pptf(v,k,limt,iter,pp,pv)=
{
gata=0;
a=0;  /*not necessary*/
pr=prod(i=1,#v,v[i]);
while(k<li
I did this long ago, if you have trouble with some of them, give me a sign.

I am currently playing with implementing P-1 on cuda. For that, I started with a pari implementation, to see how the things go around. If you are interested in going "deeper" with the "filtering", then you can play with the next pari script too:
[edit limit, I cut it out, let's see with attach]
[grr need to rename it txt]
Attached Files m_pollard.gp.txt (11.4 KB, 163 views)   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post rcv FactorDB 1 2017-10-02 06:18 clowns789 Operation Billion Digits 574 2017-09-12 01:34 a1call Miscellaneous Math 179 2015-11-12 14:59 Stargate38 Factoring 24 2011-11-03 00:34 Unregistered Information & Answers 7 2010-08-12 06:25

All times are UTC. The time now is 12:35.

Fri Aug 7 12:35:43 UTC 2020 up 21 days, 8:22, 1 user, load averages: 2.56, 2.58, 2.43