Trial Factoring backwards - Page 2

frmky · 2011-11-26, 07:03

Quote:

Originally Posted by axn

The latter. For comparison, computing Ord_2 for the first 10^5 primes > 2^65 takes PARI about 9min. That's about 4.5 order-of-magnitude shy of 10^7 primes/sec.

Mathematica took 172 seconds to compute the order for 10^5 primes between 2^65 and 2^66.

ATH · 2011-11-26, 17:20

Since q is prime ord_p(2) = q. But ord_p(2) is a factor of phi(p)=p-1.

So for each prime p, we trialfactor p-1 up to 1 billion and check if any of the factors found are ord_p(2) ?

akruppa · 2011-11-26, 20:44

For each prime power q^k || p-1 you find, you can look for the largest 0 <= i <= k for which 2^((p-1)/q^i) == 1 (mod p); then q^(k-i) exactly divides ord_p(2). Since ((p-1)/something) will include the same prime factors over and over again, maybe it's worthwhile to build some kind of tree. Then again, taking powers of 2 modulo a relatively small prime is pretty fast already, the tree might lose due to overhead.

ATH · 2011-11-27, 04:43

I am still missing how ord_p(2) can be composite?

If p | Mq => 2^q = 1 (mod p) => q = k*ord_p(2), but since we are only interested in q prime then k=1 and ord_p(2) is prime and equal to q?

So if p-1 = r₁^k₁ * r₂^k₂ * ... * r_n^k_n then we only need to check if ord_p(2) is r₁, r₂... up to 1 billion?

LaurV · 2011-11-27, 06:42

Ord(2,M=2^p-1) it is always p, which is prime. Ord(2,q), where q divides M it is always p, no matter if q is prime or not. There is a simple theorem saying that ord(x,a*b)=lcm(ord(x,a),ord(x,b)) for x prime and any a,b.

Ex: Ord(2,2^29-1)=29. Because the smallest power you need to raise 2 to get 1 mod M, is 29. There is no other smaller power. Therefore, ord(2,233)=29, ord(2,1103)=29, ord(2,2089)=29, ord(2,233*1103)=29, and so on. If any of them would be different, then by the LCM theorem above we would get ord(2,M)>29, which is impossible.

Generally, ord(2,q) can be composite. Ord(2,73)=9, ord(2,13)=12, etc.

I played with these things long time ago. I was hunting factors of mersenne numbers Mp not by p, but by k in 2*k*p+1. Still have the files with all factors below 2^56 or so, for all exponents under 10 billions. I also tried (random) higher numbers (see here some discussion) and sometime got lucky to find a factor after hours of (random) search. The problem with this method is EXACTLY one described by akruppa in post #3 above, in this thread. The method is feasible under approximatively 2^56 (for the factor q, not for k) with a HIGHLY optimized program (for CPU). For the pari script presented in the link above, the cut-off is somewhere between 2^29 and 2^33, depending of how fast is your computer. Over this limits, you will try TOO MANY numbers q whose order is q-1, or (q-1)/2 (the most of the primes, even if you filter them by 8k $\pm$ 1) which are NOT INTERESTED for our domain (lower then a billion).

akruppa · 2011-11-27, 11:28

ATH, yes, if you want to restrict reported factors to those of Mersenne numbers with prime exponent, then just check whether 2^q==1(mod p) for each prime factor q of p-1.

2011-11-26, 20:44	#14
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	For each prime power q^k \|\| p-1 you find, you can look for the largest 0 <= i <= k for which 2^((p-1)/q^i) == 1 (mod p); then q^(k-i) exactly divides ord_p(2). Since ((p-1)/something) will include the same prime factors over and over again, maybe it's worthwhile to build some kind of tree. Then again, taking powers of 2 modulo a relatively small prime is pretty fast already, the tree might lose due to overhead. Last fiddled with by akruppa on 2011-11-26 at 20:50

2011-11-27, 04:43	#15
ATH Einyen Dec 2003 Denmark 2×1,579 Posts	I am still missing how ord_p(2) can be composite? If p \| Mq => 2^q = 1 (mod p) => q = kord_p(2), but since we are only interested in q prime then k=1 and ord_p(2) is prime and equal to q? So if p-1 = r₁^k₁ r₂^k₂ * ... * r_n^k_n then we only need to check if ord_p(2) is r₁, r₂... up to 1 billion? Last fiddled with by ATH on 2011-11-27 at 04:47

2011-11-27, 06:42	#16
LaurV Romulan Interpreter Jun 2011 Thailand 7²·197 Posts	Ord(2,M=2^p-1) it is always p, which is prime. Ord(2,q), where q divides M it is always p, no matter if q is prime or not. There is a simple theorem saying that ord(x,ab)=lcm(ord(x,a),ord(x,b)) for x prime and any a,b. Ex: Ord(2,2^29-1)=29. Because the smallest power you need to raise 2 to get 1 mod M, is 29. There is no other smaller power. Therefore, ord(2,233)=29, ord(2,1103)=29, ord(2,2089)=29, ord(2,2331103)=29, and so on. If any of them would be different, then by the LCM theorem above we would get ord(2,M)>29, which is impossible. Generally, ord(2,q) can be composite. Ord(2,73)=9, ord(2,13)=12, etc. I played with these things long time ago. I was hunting factors of mersenne numbers Mp not by p, but by k in 2kp+1. Still have the files with all factors below 2^56 or so, for all exponents under 10 billions. I also tried (random) higher numbers (see here some discussion) and sometime got lucky to find a factor after hours of (random) search. The problem with this method is EXACTLY one described by akruppa in post #3 above, in this thread. The method is feasible under approximatively 2^56 (for the factor q, not for k) with a HIGHLY optimized program (for CPU). For the pari script presented in the link above, the cut-off is somewhere between 2^29 and 2^33, depending of how fast is your computer. Over this limits, you will try TOO MANY numbers q whose order is q-1, or (q-1)/2 (the most of the primes, even if you filter them by 8k $\pm$ 1) which are NOT INTERESTED for our domain (lower then a billion). Last fiddled with by LaurV on 2011-11-27 at 06:44

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Trial Factoring on AMD/ATI GPU's?	Stargate38	GPU Computing	9	2018-08-31 07:58
What is Trial Factoring?	Unregistered	Information & Answers	5	2012-08-02 03:47
over trial factoring	JFB	Software	23	2004-08-22 05:37
Trial factoring	Citrix	Software	7	2004-02-26 03:24
About trial factoring	gbvalor	Math	4	2003-05-22 02:04

2011-11-26, 17:20	#13
ATH Einyen Dec 2003 Denmark 2·1,579 Posts	Since q is prime ord_p(2) = q. But ord_p(2) is a factor of phi(p)=p-1. So for each prime p, we trialfactor p-1 up to 1 billion and check if any of the factors found are ord_p(2) ?

2011-11-27, 11:28	#17
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	ATH, yes, if you want to restrict reported factors to those of Mersenne numbers with prime exponent, then just check whether 2^q==1(mod p) for each prime factor q of p-1.