mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-11-09, 22:27   #12
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

134310 Posts
Default

In the example given in the Wiki, only step 1 is done. Note that according to the last paragraph of the "Step 1" section, the exponent of the Mersenne number will divide p-1, so that exponent is included as well when computing the value E, so step 2 is not needed in this case.
alpertron is offline   Reply With Quote
Old 2011-11-10, 06:18   #13
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

220738 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This is false. <snip>
This is JUST A COINCIDENCE and can not be relied upon.
This is not false, and it is not a coincidence. I may not understand number field sieve algorithm, but the basic algorithms I understand by heart, I can prove everything, and also I did different implementation for them with small numbers to check if I understood, at the time when I was learning about them. This is up to (and including) quadratic sieve.

All this basic algorithms (including P-1) are very easy to understand assuming one knows basic algebra and Fermat's little theorem (FT). You do not need anything else (I do not mean you personally, I mean in general, and I am convinced that you personally know these facts much better than me and than anyone here!) .

Basic algebra tells us that any poly of the form a^{2n}-b^{2n} can be decomposed into (a^n-b^n)(a^n+b^n) and FT tells us that for any prime p and any a coprime with p we have (I pick the form most convenient here) a^{p-1}-1=0 mod p.

So the order of any x in any prime p is a factor of p-1. If you multiply two p's together to get n, then the order of x in n is LCM of the two orders, that turns out to be a factor of LCM(p1-1, p2-1). Now, for a mersenne number m, all factors are 2*k*p+1, so the order of any x in m is a factor of LCM(2*ki*p, for all i). This order is what P-1 tries to find, taking x=3. This number may contain p, or it may not, if you like (what really happens can be seen, considering the fact that all factors of m are either 8k+1 or 8k-1, and the 8k-1 factors exist always, and they are in an odd number, this is a simple exercise) but this is not important now.

If m has a factor q, P-1 will find this factor if q-1 is B-smooth. Due to the form of the factors, you can place p in the product from the beginning (in fact you can place 2*p there, because if you get 3^(2*P*E)=1, you go back step by step - see the "basic algebra" reference above) and this is how you reduce the problem from "q-1 being B-smooth" to "k being B-smooth".

From this link: "This method when adapted to Mersenne numbers is even more effective. Remember, that the factor q is of the form 2kp+1. It is easy to modify the P-1 method such that it will find the factor q whenever k is highly composite."

This is how you "modify" it.

That is, in fact, what I intended to say in the previous post. I can detail it (at the "entry level") if some beginner is interested. I am not intending to teach you math. You may consider the fact that for many of us, your math language is too advanced. So, let us talk our language.

Last fiddled with by LaurV on 2011-11-10 at 06:28
LaurV is offline   Reply With Quote
Old 2011-11-10, 06:21   #14
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

52·7·53 Posts
Default

Quote:
Originally Posted by alpertron View Post
In the example given in the Wiki, only step 1 is done. Note that according to the last paragraph of the "Step 1" section, the exponent of the Mersenne number will divide p-1, so that exponent is included as well when computing the value E, so step 2 is not needed in this case.
This formulation is a bit ambiguous, the exponent is p, that does not divide p-1.
LaurV is offline   Reply With Quote
Old 2011-11-10, 07:33   #15
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

I would be interested in less advanced vocabulary. As has been discussed elsewhere, I've never studied and sort of number theory in any depth at all, and I have no idea what "order" means, and after that is where I get seriously lost. (Also, if p is prime, wouldn't any integer a be coprime to p?)
Dubslow is offline   Reply With Quote
Old 2011-11-10, 07:39   #16
axn
 
axn's Avatar
 
Jun 2003

12F816 Posts
Default

Quote:
Originally Posted by Dubslow View Post
I would be interested in less advanced vocabulary. As has been discussed elsewhere, I've never studied and sort of number theory in any depth at all, and I have no idea what "order" means, and after that is where I get seriously lost.
http://en.wikipedia.org/wiki/Order_%28group_theory%29 -- Best not to tackle it at this point, though.
Anyways, to understand P-1 algo, you don't need to know about orders and stuff.
Quote:
Originally Posted by Dubslow View Post
(Also, if p is prime, wouldn't any integer a be coprime to p?)
p, 2p, 3p, 4p, ...

Last fiddled with by axn on 2011-11-10 at 07:42 Reason: Don't forget 1p
axn is offline   Reply With Quote
Old 2011-11-10, 09:47   #17
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default

Quote:
Originally Posted by Dubslow View Post
I would be interested in less advanced vocabulary. As has been discussed elsewhere, I've never studied and sort of number theory in any depth at all, and I have no idea what "order" means, and after that is where I get seriously lost. (Also, if p is prime, wouldn't any integer a be coprime to p?)
Here's how the P-1 algorithm works, without reference to "group order", and with modular arithmetic rendered into ordinary arithmetic.

Let E be a composite number. Let p be a prime number such that p-1 divides E. Specifically let p-1 = E/b for some integer b. Let a be an integer coprime to p.

Fermat's Little Theorem states that ap-1 \equiv 1 (mod p). This is equivalent to the statement that p divides ap-1-1.

Elementary algebra tells us that aE-1 = ab(p-1)-1 is divisible by ap-1-1.

Hence p divides aE-1. It should be noted that, for values of E large enough to be useful, aE-1 is an incalculably large number. What we can compute, without computing aE-1, is a small number congruent to it modulo N, i.e., (aE-1) - cN for some integer c. If p divides N, then p divides both terms, therefore divides their difference.

Therefore p divides GCD((aE-1) - cN, N). This GCD may be N, in which case the algorithm has failed, otherwise it will be a (possibly composite) non-trivial proper factor of N.

I hit submit too soon. What I haven't covered in the above, is the appropriate choice of E.

Last fiddled with by Mr. P-1 on 2011-11-10 at 10:04
Mr. P-1 is offline   Reply With Quote
Old 2011-11-10, 12:03   #18
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7·167 Posts
Default

Quote:
Originally Posted by Mr. P-1 View Post
I hit submit too soon. What I haven't covered in the above, is the appropriate choice of E.
In the above, I made no assumptions about E other than that it was composite and it had at least one factor one less than a prime. In order to be useful, we need to choose E so that it has many factors each one less than a possible prime factor of N. (Other factors of E which do not satisfy this criterion are harmless.) If N is such that its factors have known divisibility properties, such as the 2kq+1 form of the factors of the Mersenne number Mq, then these divisors must be divisors of E in order for the algorithm to have a chance of finding any factors at all. So let E = E' * (known divisors of p-1). Imagine constructing E' by starting with 1 and successively multiplying in primes ri, each chosen to give the maximum benefit to cost ratio available.

E0 = 1
Ei = Ei-1 * ri

Each new prime ri increases the size of E' (hence of E) by log2(ri) bits. This is proportional to the increase in the cost of the computation.

The benefit of including ri will be proportional to ri-k[sub]i[/sub], where ki is the multiplicity of ri in Ei.

The benefit is therefore hugely sensitive to the choice of ri, while the cost is relatively insensitive to that choice. To a first approximation, the best ri will be the one that minimises rik[sub]i[/sub].

The end result will be that, for any i, the powers of each prime factor r of Ei will be as close as possible. The choice usually implemented, which is that given in the wiki, is to make E' equal to the product of all primes powers less than some B1. This is near optimal. We call the computation of a small number congruent to aE-1 so chosen "stage 1".

Stage 2 involves computing a small number congruent to (as[sub]1[/sub]*E-1)(as[sub]2[/sub]*E-1)(as[sub]2[/sub]*E-1)... for recessive primes sj between B1 and some B2. Each of the terms in the product substitutes s2*E for E in the stage 1 computation and finds any prime factor p=k*(known divisors) + 1 if k is divisible by s2 and k/s2 is power-smooth to B1. Computing a small number congruent to any term in the product individually would be tantamount to choosing a non-optimal choice of E for stage 1, and would not be cost effective, but using the method described in the wiki, and other tricks and techniques not described there, small numbers congruent to successive terms in the product can be calculated quite cheaply.

Last fiddled with by Mr. P-1 on 2011-11-10 at 12:18
Mr. P-1 is offline   Reply With Quote
Old 2011-11-10, 14:35   #19
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default Can I have a "p" please, Bob?

Quote:
Originally Posted by axn View Post
Remember that for mersennes, you're allowed a 'p' for free.
What! Not even a penny?

David
davieddy is offline   Reply With Quote
Old 2011-11-18, 11:11   #20
Maximus
 
Nov 2011

22×3 Posts
Question How does P95 perform stage 1?

Does P95 in stage 1 of p-1 factoring:
- calculate E=p1*p2*p3*...., then calculate a^E mod N;
- or calculate a1=a^p1 mod N, then a2=a1^p2 mod N, then a3=a2^p3 mod N, and so on;
- or another way?
p1, p2, p3, ... means powers of primes less then B1.
Who can tell, please?

Last fiddled with by Maximus on 2011-11-18 at 11:17
Maximus is offline   Reply With Quote
Old 2011-11-18, 11:19   #21
axn
 
axn's Avatar
 
Jun 2003

113708 Posts
Default

Quote:
Originally Posted by Maximus View Post
Does P95 in stage 1 of p-1 factoring:
- calculate E=p1*p2*p3*...., then calculate a^E mod N;
- or calculate a1=a^p1 mod N, then a2=a1^p2 mod N, then a3=a2^p3 mod N, and so on;
- or another way?
p1, p2, p3, ... means powers of primes less then B1.
Who can tell, please?
For the initial set of smaller primes, it uses the first method. Then switches over to the second method. You can look at the source yourselves.
http://www.mersenneforum.org/gimps/ (look in ecm.c)
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A doubt about the correctness of the Four Colour Theorem Raman Puzzles 4 2016-12-25 06:55
doubt with PARI and modular operations skan Software 16 2013-04-01 16:54
TF algorithm(s) davieddy Miscellaneous Math 61 2011-07-06 20:13
Is there an algorithm which solves this? Unregistered Homework Help 0 2007-08-09 17:40
Maybe new sieving algorithm nuggetprime Riesel Prime Search 5 2007-04-20 04:19

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

Fri Mar 5 20:48:52 UTC 2021 up 92 days, 17 hrs, 0 users, load averages: 1.60, 1.86, 2.28

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.