20111109, 22:27  #12 
Aug 2002
Buenos Aires, Argentina
3×5×97 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 p1, so that exponent is included as well when computing the value E, so step 2 is not needed in this case.

20111110, 06:18  #13  
Romulan Interpreter
"name field"
Jun 2011
Thailand
37·271 Posts 
Quote:
All this basic algorithms (including P1) 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 p1. 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(p_{1}1, p_{2}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*k_{i}*p, for all i). This order is what P1 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 8k1, and the 8k1 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, P1 will find this factor if q1 is Bsmooth. 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 "q1 being Bsmooth" to "k being Bsmooth". 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 P1 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 20111110 at 06:28 

20111110, 06:21  #14  
Romulan Interpreter
"name field"
Jun 2011
Thailand
37×271 Posts 
Quote:


20111110, 07:33  #15 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
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?)

20111110, 07:39  #16  
Jun 2003
2^{2}·3·449 Posts 
Quote:
Anyways, to understand P1 algo, you don't need to know about orders and stuff. p, 2p, 3p, 4p, ... Last fiddled with by axn on 20111110 at 07:42 Reason: Don't forget 1p 

20111110, 09:47  #17  
Jun 2003
2221_{8} Posts 
Quote:
Let E be a composite number. Let p be a prime number such that p1 divides E. Specifically let p1 = E/b for some integer b. Let a be an integer coprime to p. Fermat's Little Theorem states that a^{p1} 1 (mod p). This is equivalent to the statement that p divides a^{p1}1. Elementary algebra tells us that a^{E}1 = a^{b(p1)}1 is divisible by a^{p1}1. Hence p divides a^{E}1. It should be noted that, for values of E large enough to be useful, a^{E}1 is an incalculably large number. What we can compute, without computing a^{E}1, is a small number congruent to it modulo N, i.e., (a^{E}1)  cN for some integer c. If p divides N, then p divides both terms, therefore divides their difference. Therefore p divides GCD((a^{E}1)  cN, N). This GCD may be N, in which case the algorithm has failed, otherwise it will be a (possibly composite) nontrivial 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. P1 on 20111110 at 10:04 

20111110, 12:03  #18  
Jun 2003
7×167 Posts 
Quote:
E_{0} = 1 E_{i} = E_{i1} * r_{i} Each new prime r_{i} increases the size of E' (hence of E) by log_{2}(r_{i}) bits. This is proportional to the increase in the cost of the computation. The benefit of including r_{i} will be proportional to r_{i}^{k[sub]i[/sub]}, where k_{i} is the multiplicity of r_{i} in E_{i}. The benefit is therefore hugely sensitive to the choice of r_{i}, while the cost is relatively insensitive to that choice. To a first approximation, the best r_{i} will be the one that minimises r_{i}^{k[sub]i[/sub]}. The end result will be that, for any i, the powers of each prime factor r of E_{i} 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 a^{E}1 so chosen "stage 1". Stage 2 involves computing a small number congruent to (a^{s[sub]1[/sub]*E}1)(a^{s[sub]2[/sub]*E}1)(a^{s[sub]2[/sub]*E}1)... for recessive primes s_{j} between B1 and some B2. Each of the terms in the product substitutes s_{2}*E for E in the stage 1 computation and finds any prime factor p=k*(known divisors) + 1 if k is divisible by s_{2} and k/s_{2} is powersmooth to B1. Computing a small number congruent to any term in the product individually would be tantamount to choosing a nonoptimal 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. P1 on 20111110 at 12:18 

20111110, 14:35  #19 
"Lucan"
Dec 2006
England
2×3×13×83 Posts 
Can I have a "p" please, Bob?

20111118, 11:11  #20 
Nov 2011
2^{2}×3 Posts 
How does P95 perform stage 1?
Does P95 in stage 1 of p1 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 20111118 at 11:17 
20111118, 11:19  #21  
Jun 2003
5388_{10} Posts 
Quote:
http://www.mersenneforum.org/gimps/ (look in ecm.c) 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A doubt about the correctness of the Four Colour Theorem  Raman  Puzzles  4  20161225 06:55 
doubt with PARI and modular operations  skan  Software  16  20130401 16:54 
TF algorithm(s)  davieddy  Miscellaneous Math  61  20110706 20:13 
Is there an algorithm which solves this?  Unregistered  Homework Help  0  20070809 17:40 
Maybe new sieving algorithm  nuggetprime  Riesel Prime Search  5  20070420 04:19 