20180307, 11:36  #1 
Feb 2018
2^{5}·3 Posts 
Whats is a fast algorithm for compute znorder(Mod(2,p)).
whats is a fast algorithm for compute znorder(Mod(2,p)).
for p prime but big. Last fiddled with by JM Montolio A on 20180307 at 11:45 
20180307, 11:40  #2 
"Forget I exist"
Jul 2009
Dumbassville
10000011000000_{2} Posts 

20180307, 11:46  #3 
Feb 2018
2^{5}×3 Posts 
You never sleeps ?

20180307, 15:10  #4  
Aug 2006
3×1,993 Posts 
Quote:
For example, let's try to find the order of 2 mod 101. m = 100 = 2^2 * 5^2, so we know that 2^100 = 1 mod 101. 2^(100/2) mod 101 is 100 which is not 1, so skip 2. 2^(100/5) = 95 which is not 1, so skip 5, and we're done: the order is 100. Let's try 103. m = 102 = 2 * 3 * 17. 2^(102/2) = 1 mod 103, so m becomes 102/2 = 51. We don't have any more 2s though so we'll go on to 3. 2^(51/3) = 56 mod 103 which is not 1, and 2^(51/17) = 8 mod 103 which is also not 1, so we're done: the order of 2 mod 103 is 51. 

20190612, 01:44  #6 
Apr 2019
5·41 Posts 
Um, if p is prime, isn't the answer always p1?
edit: nevermind, i'm obviously confused Last fiddled with by hansl on 20190612 at 01:50 
20190612, 16:09  #7 
Aug 2006
3·1,993 Posts 

20190612, 17:46  #8  
"Robert Gerbicz"
Oct 2005
Hungary
1,531 Posts 
Quote:
Code:
res_i=2^((p1)/q^i) mod p for i=e,e1,..1,0 Multiply these primepowers to get the order. Note that you really need some intelligence here also, because there could be more than polynomial number of divisors of p1. 

20190612, 19:02  #9 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{2}×2,423 Posts 

20190613, 11:46  #10  
Feb 2017
Nowhere
3×1,787 Posts 
Quote:
As is well known (supplement to the quadratic reciprocity law), znorder(Mod(2,p)) divides (p1)/2 if p == 1 or 7 (mod 8), but not otherwise. Since 101 == 5 (mod 8) we know that znorder(Mod(2,101)) does not divide 100/2 = 50. Since 103 = 7 (mod 8) we know that znorder(Mod(2,103)) does divide 102/2 = 51. Alas, the classical criterion of when znorderMod(2,p)) divides (p1)/4 when 8 divides p1 [p = x^2 + 64*y^2] likely takes longer to decide than whether Mod(2,p)^((p1)/4) == Mod(1,p). Likewise, the classical criterion for whether znorder(Mod(2,p)) divides (p1)/3 when 3 divides p1 [p = x^2 + 27*y^2] is likely also slower than computing Mod(2,p)^(p1)/3 when 3 divides p1. 

20190614, 03:13  #11 
Aug 2006
5979_{10} Posts 
We’re not disagreeing here of course: the factorization takes up asymptotically all the time (in the worst/average case), but for me the heart of the problem is what I described in my post, and the factorization is a (difficult) subproblem that must be resolved before moving on to that core part.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Do normal adults give themselves an allowance? (...to fast or not to fast  there is no question!)  jasong  jasong  35  20161211 00:57 
Whats the next prime?  Dougal  Puzzles  5  20090823 20:16 
Whats the best stress test settings for RAM stability?  xtreme2k  Hardware  6  20070328 20:38 
Whats going on in the background  ltd  Prime Sierpinski Project  2  20061226 09:40 
Whats the worst (harshest scenario) for torture test?  xtreme2k  Hardware  9  20040714 18:41 