mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > PrimeNet

Reply
 
Thread Tools
Old 2019-06-18, 13:30   #474
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3·23·43 Posts
Default

Yes, you do 21723 mod q and 22447 mod q and see if you get 1.
ATH is offline   Reply With Quote
Old 2019-06-18, 14:24   #475
2M215856352p1
 
May 2019

113 Posts
Default Another possible method of factoring by q

Factors of 2^p-1 for p prime are in the form q=2*k*p+1 for some non-negative integer k.

Initialisation/Initialization
Step 1. For each prime p on the interval [pmin, pmax], we find the smallest q>=qmin such that 2p divides q-1, and push the corresponding tuple (q, p) into a priority queue.

Main logic
Step 2: Retrieve and pop the smallest (q, p) tuple out of the priority queue. To optimise, we check if a small prime (say at most m) divides q by computing q mod m# and precomputing a list of possible remainders mod m#. Check if q divides 2^p-1. If it does, output the corresponding (q, p). Insert (q+2p, p) inside the priority queue.

This avoids the trial factoring step. As Gerbicz pointed out, pmin should be at least 10^6 since exponents with factoring done have been deeply trial factored and/or ECMed.

If I have made a mistake, please correct me.

Last fiddled with by 2M215856352p1 on 2019-06-18 at 14:25
2M215856352p1 is offline   Reply With Quote
Old 2019-06-18, 14:46   #476
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·3·739 Posts
Default

Where is the difference to "by p", except that your method is much MUCH slower?
This is what GIMPS does, except that each p has "its own queue" and "there is no physical queue".

The issue is that your method tests (almost) all k's and most of them no need to be tested at all (ex: k=2 mod 4 should never be tested, also k=p mod 4 should not be tested, etc).

Last fiddled with by LaurV on 2019-06-18 at 14:49
LaurV is offline   Reply With Quote
Old 2019-06-18, 15:03   #477
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×3×13×59 Posts
Default

Quote:
Originally Posted by DukeBG View Post
Um, you don't need to divide that. You just calculate the ModPow (with all the speed improvements). Unless that is what you implied?
Right, for novices reading here, it's good you point that out. Long division is not the method of trial of a factor candidate. Raising 2 to the p power, mod the candidate factor along the way, is. It's far faster since it keeps the operands limited to dozens of bits in size, rather than thousands or millions or hundreds of millions. If 2p mod f is 1, 2p-1 mod f is zero and f is shown to be a factor of 2p-1.
ATH's descriptions should be understood as simplified overviews. There's quite a lot to the by-p method used in mfaktc, mfakto, and elsewhere. See https://www.mersenneforum.org/showpo...23&postcount=6

Last fiddled with by kriesel on 2019-06-18 at 15:17
kriesel is online now   Reply With Quote
Old 2019-06-18, 15:14   #478
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

5,807 Posts
Default

Quote:
Originally Posted by kriesel View Post
Raising 2 to the p power, mod the candidate factor along the way, is. It's far faster since it keeps the operands limited to dozens of bits in size, rather than thousands or millions or hundreds of millions. If 2p mod f is 1, 2p-1 mod f is zero and f is shown to be a factor of 2p-1.
Long division would always shift in a new '1' bit at each step, so we don't need to store the entire number. The reason is not the size of the operands, but because there is a simple method that allows us to do powers in many fewer steps than it would take if we did naive division.

Last fiddled with by retina on 2019-06-18 at 15:14
retina is offline   Reply With Quote
Old 2019-06-18, 15:58   #479
2M215856352p1
 
May 2019

1618 Posts
Default

Quote:
Originally Posted by LaurV View Post
Where is the difference to "by p", except that your method is much MUCH slower?
This is what GIMPS does, except that each p has "its own queue" and "there is no physical queue".

The issue is that your method tests (almost) all k's and most of them no need to be tested at all (ex: k=2 mod 4 should never be tested, also k=p mod 4 should not be tested, etc).
My method consumes more memory and the factors will be found in increasing order.
2M215856352p1 is offline   Reply With Quote
Old 2019-06-22, 13:04   #480
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·3·13·59 Posts
Default

Quote:
Originally Posted by retina View Post
Long division would always shift in a new '1' bit at each step, so we don't need to store the entire number. The reason is not the size of the operands, but because there is a simple method that allows us to do powers in many fewer steps than it would take if we did naive division.
Fully naive long division would be equivalent to how it is taught in school for general base 10 numbers, with the entire dividend present in memory versus on paper (storage) at the outset. Good point that it's perhaps wasted space for a mersenne number in binary; we know it's all ones so generating additional rightward bits on the fly as needed is simple. Sometimes space is traded for speed, including in naive algorithms. It might be that adding them a word width at a time in long division is less inefficient.

Last fiddled with by kriesel on 2019-06-22 at 13:07
kriesel is online now   Reply With Quote
Old 2019-06-22, 14:06   #481
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·3·13·59 Posts
Default

Quote:
Originally Posted by retina View Post
Long division would always shift in a new '1' bit at each step, so we don't need to store the entire number. The reason is not the size of the operands, but because there is a simple method that allows us to do powers in many fewer steps than it would take if we did naive division.
Thanks, updated #12 of https://www.mersenneforum.org/showpo...23&postcount=6
kriesel is online now   Reply With Quote
Old 2019-06-22, 14:45   #482
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

5,807 Posts
Default

Quote:
Originally Posted by kriesel View Post
Fully naive long division would be equivalent to how it is taught in school for general base 10 numbers, with the entire dividend present in memory versus on paper (storage) at the outset. Good point that it's perhaps wasted space for a mersenne number in binary; we know it's all ones so generating additional rightward bits on the fly as needed is simple. Sometimes space is traded for speed, including in naive algorithms. It might be that adding them a word width at a time in long division is less inefficient.
Quote:
Originally Posted by kriesel View Post
We also don't care about the quotient so even if we did long division we can simply throw away the quotient and the final step reveals the remainder. So memory usage is of no concern here. Even if you did steps of 32-bits, or 64-bits, or whatever, this only gives a linear speed-up.

Last fiddled with by retina on 2019-06-22 at 14:47
retina is offline   Reply With Quote
Old 2019-08-21, 13:44   #483
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

31·43 Posts
Default

Today TJAOI finished finding prime factors less than 266.

The last one is the prime factor 73786932973062531511 of M193866301 (65.99999915 bits)
alpertron is offline   Reply With Quote
Old 2019-08-23, 23:32   #484
Madpoo
Serpentine Vermin Jar
 
Madpoo's Avatar
 
Jul 2014

29·113 Posts
Default

Quote:
Originally Posted by alpertron View Post
Today TJAOI finished finding prime factors less than 266.

The last one is the prime factor 73786932973062531511 of M193866301 (65.99999915 bits)
I don't know who that user is, but if I ever meet him/her, I'll buy 'em a drink of their choice.
Madpoo is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Old User Unregistered Information & Answers 1 2012-10-18 23:31
The user CP has gone :( retina Forum Feedback 5 2006-12-05 16:47
Changing My User ID endless mike NFSNET Discussion 1 2004-10-31 19:38
OSX yet? new user here KevinLee Hardware 6 2003-12-12 17:06
help for a Mac user drakkar67 Software 3 2003-02-11 10:55

All times are UTC. The time now is 20:51.

Sat Oct 24 20:51:58 UTC 2020 up 44 days, 18:02, 0 users, load averages: 1.87, 1.84, 1.76

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.