 mersenneforum.org Doubt about P-1 algorithm
 Register FAQ Search Today's Posts Mark Forums Read  2011-11-09, 22:27 #12 alpertron   Aug 2002 Buenos Aires, Argentina 22·3·112 Posts 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.   2011-11-10, 06:18   #13
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

997310 Posts Quote:
 Originally Posted by R.D. Silverman This is false. 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 can be decomposed into and FT tells us that for any prime p and any a coprime with p we have (I pick the form most convenient here) 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   2011-11-10, 06:21   #14
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

9,973 Posts Quote:
 Originally Posted by alpertron 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.   2011-11-10, 07:33 #15 Dubslow Basketry That Evening!   "Bunslow the Bold" Jun 2011 40 2011-11-10, 07:39   #16
axn

Jun 2003

150116 Posts Quote:
 Originally Posted by Dubslow 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 (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   2011-11-10, 09:47   #17
Mr. P-1

Jun 2003

7·167 Posts Quote:
 Originally Posted by Dubslow 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 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   2011-11-10, 12:03   #18
Mr. P-1

Jun 2003

49116 Posts Quote:
 Originally Posted by Mr. P-1 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   2011-11-10, 14:35   #19
davieddy

"Lucan"
Dec 2006
England

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

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

David   2011-11-18, 11:11 #20 Maximus   Nov 2011 22·3 Posts 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   2011-11-18, 11:19   #21
axn

Jun 2003

537710 Posts Quote:
 Originally Posted by Maximus 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)   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Raman Puzzles 4 2016-12-25 06:55 skan Software 16 2013-04-01 16:54 davieddy Miscellaneous Math 61 2011-07-06 20:13 Unregistered Homework Help 0 2007-08-09 17:40 nuggetprime Riesel Prime Search 5 2007-04-20 04:19

All times are UTC. The time now is 08:38.

Mon Jul 4 08:38:42 UTC 2022 up 81 days, 6:40, 0 users, load averages: 1.32, 1.16, 1.11