Factors of Mersenne numbers ? - Page 2

Fusion_power · 2003-10-26, 21:28

Dsouza,

Ubasic is a very limited language. Its maximum precision is about 2800 digits.

If I were trying to do high precision integer math with 10,000,000 or more digits, I would probably be facing a custom program.

Ubasic happened to be a very available language that is very similar to the old IBM basic with which I am reasonably familiar. I wrote the above routines in about 30 minutes last night. George suggested (in an email) using it.

The problem you run into is that going from a 10 digit number to a 13 digit number takes 1000 times as long to test. This means the routines I wrote above won't be much use for numbers over say 25 digits in length because it will take so long to test such a number. Why? well because the routine tries to test every possible factor of the trial number.

I'm working on an optimization of the above code to test mersenne numbers. It should be ready to go in another few hours.

Fusion

dsouza123 · 2003-10-27, 04:15

Thanks for the GMP (GNU MP Bignum) link. I use Windows so it would be quite involved to use ( in C, and use gcc, cygwin, mingw, etc ). Will look at the code though.

The calculator is very fast, tested a trial factor
(2^22282517 - 1) mod 5393976387915192439 and it came back with result 0 said it took 0 ms.

Trial factoring really does have quite a bit of code that uses the FPU, some is integer but most is floating point.

For the sieve, initializing and other stuff, especially 61+ bits.

See factor64.asm

dsouza123 · 2003-10-28, 20:52

posted this in programming, just copied/elaborated it in this thread because there was some code here already.

It uses the mod of a base to a power (2^P mod Q) with a check for remainder=1, instead of the powering algorithm which is used in prime95. uBasic can have integer variables of 540 15 bit words in size (around 8100 bits (may be some other overhead)).
I haven't tried it ( for very long ) on mersennes in the range that are being tested currently so I don't know how long it would take.

A test example is P = 22282517 the factor Q for it is 5393976387915192439

A shortcut quick test ( ONLY for the above number P ) would be to insert the following lines ( in place by numerical order )

1075 P=22282517
1225 Q=Q+(PP*121036065800)

then it will only take a few repeat loops to finish.

Here is a short program that will do trial factoring in uBasic

1000 B=2
1050 input "2^P-1 P=";P
1100 PP=P*2
1150 D%=0
1200 Q=PP+1
1250 REPEAT
1300 M8=Q@8
1350 IF ((1=M8) OR (7=M8)) THEN IF (1=modpow(B,P,Q)) THEN D%=1:PRINT Q;" is a factor of 2^";P;" - 1"
1400 Q=Q+PP
1650 UNTIL D%

It will run until it finds a factor.
Filters factor Q so only Q MOD 8 = 1,7 will be tested.

I ran it using UBASIC86(32) for IBM-PC version 8.8f
(use ?version to get the version info)
the program filename is ubibm32.exe

A short test to limit it to a bit depth could be added to stop testing. Insert the lines of code where the line number would be in numerical order.

1115 input "Test ceiling (max number) 2^bit depth BD=";BD
1125 TC=2^BD

using 2^68 will allow testing all filtered factors below 2^68

1450 IF Q > TC THEN D%=1

d% is the short variable that determines if repeat loop is done.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
P-1 factoring attempts at smallest-remaining Mersenne numbers with no known factors	UberNumberGeek	Factoring	51	2017-02-13 20:30
Modular restrictions on factors of Mersenne numbers	siegert81	Math	23	2014-03-18 11:50
Mersenne prime factors of very large numbers	devarajkandadai	Miscellaneous Math	15	2012-05-29 13:18
Mersenne Prime Factors of v.large numbers	devarajkandadai	Miscellaneous Math	6	2006-01-04 22:44
Factors of Mersenne Numbers	asdf	Math	17	2004-07-24 14:00

2003-10-26, 21:28	#12
Fusion_power Aug 2003 Snicker, AL 7·137 Posts	Dsouza, Ubasic is a very limited language. Its maximum precision is about 2800 digits. If I were trying to do high precision integer math with 10,000,000 or more digits, I would probably be facing a custom program. Ubasic happened to be a very available language that is very similar to the old IBM basic with which I am reasonably familiar. I wrote the above routines in about 30 minutes last night. George suggested (in an email) using it. The problem you run into is that going from a 10 digit number to a 13 digit number takes 1000 times as long to test. This means the routines I wrote above won't be much use for numbers over say 25 digits in length because it will take so long to test such a number. Why? well because the routine tries to test every possible factor of the trial number. I'm working on an optimization of the above code to test mersenne numbers. It should be ready to go in another few hours. Fusion

2003-10-27, 04:15	#13
dsouza123 Sep 2002 2·331 Posts	Thanks for the GMP (GNU MP Bignum) link. I use Windows so it would be quite involved to use ( in C, and use gcc, cygwin, mingw, etc ). Will look at the code though. The calculator is very fast, tested a trial factor (2^22282517 - 1) mod 5393976387915192439 and it came back with result 0 said it took 0 ms. Trial factoring really does have quite a bit of code that uses the FPU, some is integer but most is floating point. For the sieve, initializing and other stuff, especially 61+ bits. See factor64.asm

2003-10-28, 20:52	#14
dsouza123 Sep 2002 2·331 Posts	posted this in programming, just copied/elaborated it in this thread because there was some code here already. It uses the mod of a base to a power (2^P mod Q) with a check for remainder=1, instead of the powering algorithm which is used in prime95. uBasic can have integer variables of 540 15 bit words in size (around 8100 bits (may be some other overhead)). I haven't tried it ( for very long ) on mersennes in the range that are being tested currently so I don't know how long it would take. A test example is P = 22282517 the factor Q for it is 5393976387915192439 A shortcut quick test ( ONLY for the above number P ) would be to insert the following lines ( in place by numerical order ) 1075 P=22282517 1225 Q=Q+(PP121036065800) then it will only take a few repeat loops to finish. Here is a short program that will do trial factoring in uBasic 1000 B=2 1050 input "2^P-1 P=";P 1100 PP=P2 1150 D%=0 1200 Q=PP+1 1250 REPEAT 1300 M8=Q@8 1350 IF ((1=M8) OR (7=M8)) THEN IF (1=modpow(B,P,Q)) THEN D%=1:PRINT Q;" is a factor of 2^";P;" - 1" 1400 Q=Q+PP 1650 UNTIL D% It will run until it finds a factor. Filters factor Q so only Q MOD 8 = 1,7 will be tested. I ran it using UBASIC86(32) for IBM-PC version 8.8f (use ?version to get the version info) the program filename is ubibm32.exe A short test to limit it to a bit depth could be added to stop testing. Insert the lines of code where the line number would be in numerical order. 1115 input "Test ceiling (max number) 2^bit depth BD=";BD 1125 TC=2^BD using 2^68 will allow testing all filtered factors below 2^68 1450 IF Q > TC THEN D%=1 d% is the short variable that determines if repeat loop is done.