 mersenneforum.org > Math Residue identification algorithm
 Register FAQ Search Today's Posts Mark Forums Read  2009-08-20, 21:18 #1 SPWorley   Jul 2009 31 Posts Residue identification algorithm I'm trying to understand the identification of residues of x^n mod p, where p is an odd prime. For the residues of x^2 mod p, there are exactly (p+1)/2 residues. You can compute whether a specific value a is a quadratic residue mod p by computing the Legendre symbol (a|p). There are nice and efficient algorithms for computing (a|p) similar in feeling to Euclid's method for GCD. My question is whether there are similar methods for computing whether value a is an n-th power residue mod p? I'm especially interested in testing whether a value is a 4th power residue mod p. One method would be to test if a is a quadratic residue, and if it is, compute the square root of it (using Prime Numbers:ACP algorithm 2.3.8 for example), then testing if that root is also a quadratic residue. But that's a lot of computation, and hopefully there's an easier method! While I'm interested in a^4 residues, is there a general method for evaluating the general a^n residue case?   2009-08-20, 21:30 #2 maxal   Feb 2005 22·32·7 Posts For a prime p, a non-zero residue x modulo p is an n-th power iff x^((p-1)/gcd(p-1,n)) == 1 (mod p). In particular: For a prime p=4k+1, a non-zero residue x modulo p is a 4-th power iff x^k == 1 (mod p). For a prime p=4k+3, a non-zero residue x modulo p is a 4-th power iff it is a square (i.e., x^(2k+1) == 1 (mod p)). Last fiddled with by maxal on 2009-08-20 at 21:34   2009-08-20, 21:41   #3
SPWorley

Jul 2009

31 Posts Quote:
 Originally Posted by maxal For a prime p, a non-zero residue x modulo p is an n-th power iff x^((p-1)/gcd(p-1,n)) == 1 (mod p). In particular: For a prime p=4k+1, a non-zero residue x modulo p is a 4-th power iff x^k == 1 (mod p). For a prime p=4k+3, a non-zero residue x modulo p is a 4-th power iff it is a square (i.e., x^(2k+1) == 1 (mod p)).

This is useful, since it provides a clear general algorithm for evaluating the answer.

The annoying part is that for large p, computing x^(large) mod p is expensive. The Legendre computation method avoids such modular powers so it's super fast.
Are there any shortcuts for testing for x^n residues for n>2 like the Legendre method? Or are they all variants of computing high powers mod p?   2009-08-20, 21:52   #4
maxal

Feb 2005

22×32×7 Posts Quote:
 Originally Posted by SPWorley The annoying part is that for large p, computing x^(large) mod p is expensive.
It is not!
See http://en.wikipedia.org/wiki/Modular_exponentiation   2009-08-20, 21:58   #5
maxal

Feb 2005

22·32·7 Posts Quote:
 Originally Posted by SPWorley The Legendre computation method avoids such modular powers so it's super fast. Are there any shortcuts for testing for x^n residues for n>2 like the Legendre method?
There are some high-order reciprocity laws such as:
http://en.wikipedia.org/wiki/Cubic_reciprocity
http://en.wikipedia.org/wiki/Quartic_reciprocity
but I did not check if one can turn them into algorithms that are more efficient than modular exponentiation.

Last fiddled with by maxal on 2009-08-20 at 22:03   2009-08-20, 22:02   #6
SPWorley

Jul 2009

1F16 Posts Quote:
 Originally Posted by maxal It is not! See http://en.wikipedia.org/wiki/Modular_exponentiation
It is compared to the Legendre computation. That takes roughly log2(p)/4 mod p computes of values ~=p. The general exponentiation needs roughly 3/2 * log2(p) mod p computes of values ~= p^2, not even counting the roughly 3/2 log2(p) multiplies.   2009-08-20, 22:06   #7
SPWorley

Jul 2009

31 Posts Quote:
 Originally Posted by maxal There are some high-order reciprocity laws such as: http://en.wikipedia.org/wiki/Cubic_reciprocity http://en.wikipedia.org/wiki/Quartic_reciprocity but I did not check if one can turn them into algorithms that are more efficient than modular exponentiation.
Now that is a nearly ideal link to start exploring. I'm not sure why I didn't find it when I was searching myself.

I agree.. there's a lot of discussion there! And maybe a decent algorithm or two, but they aren't obvious (yet). But now I have something to chew on. From a 30 second skim, it's clear it's not going to be anything simple like Legendre, though..   2010-03-04, 12:26   #8
alexhiggins732

Mar 2010
Brick, NJ

67 Posts Quote:
Originally Posted by SPWorley http://www.mersenneforum.org/images/...s/viewpost.gif
The annoying part is that for large p, computing x^(large) mod p is expensive.

Quote:
 Originally Posted by maxal It is not! See http://en.wikipedia.org/wiki/Modular_exponentiation
While you are correct it is not, it is for large P. In fact the running time is slower than the Lucas with n= MP, and x = 4 because modular exponentiation would require a squaring of the base and the residue for step 0 to p-2.

I am also searching for a faster algorithm. I simply want to test whether or not a residue is an element of a modular ring.   2010-03-04, 18:09   #9
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by alexhiggins732 I am also searching for a faster algorithm. I simply want to test whether or not a residue is an element of a modular ring.
What do you mean by "element of a modular ring"???

Given an integer N > 2, then EVERY integer from 0 to N-1 is an element
of Z/NZ. And, by the standard equivalence relation, every integer is
equivalent to an element of that ring.

So the answer to your question, is in a sense, trivial. ALL
residues are an element.

If you mean something else, then you need to be more specific.   2010-03-04, 19:41 #10 alexhiggins732   Mar 2010 Brick, NJ 1038 Posts First, let me apologize before for not having the proper handle on the "language" and state that thus far I have refrained from posting on this forum as "cranks" like myself are not generally well accepted here, although I have visited this forum for some time and have been a member of GIMPS for some time as well. I also try to read as much math theory as possible but my 10th grade formal math education is quite a far gap and often find myself getting lost in with definitions written with Greek symbols often represented with a degree of ambiguity that even math Majors get confused when I ask them for definitions of what is on Wikipedia and other sites like math world. Further confusing are definitions which in which the the definition is used to defined itself, such as with the Sqrt(-1). That being said I will continue with the theorems that I have mainly developed on my which I attempt to define in your "language" with my rudimentary interpretation of what I have read and have been able to correlate my own research into While a modular ring can refer to the group of integers mod n, I am under the impression we are particularly interested in the group of integer in a particular radix to power of X mod n, which in turn lead to the reference to modular exponentiation. So to clarify my statement, lets take the MP11 and define our modular ring G2047 with elements of this modular ring being defined f(x)= 3^X Mod MP11 then we have the following: 1: 3^1 mod 2047 = 3 2: 3^2 mod 2047 = 9 3: 3^3 mod 2047 = 27 4: 3^4 mod 2047 = 81 5: 3^5 mod 2047 = 243 6: 3^6 mod 2047 = 729 7: 3^7 mod 2047 = 140 8: 3^8 mod 2047 = 420 9: 3^9 mod 2047 = 1260 10: 3^10 mod 2047 = 1733 11: 3^11 mod 2047 = 1105 12: 3^12 mod 2047 = 1268 13: 3^13 mod 2047 = 1757 14: 3^14 mod 2047 = 1177 15: 3^15 mod 2047 = 1484 16: 3^16 mod 2047 = 358 17: 3^17 mod 2047 = 1074 18: 3^18 mod 2047 = 1175 19: 3^19 mod 2047 = 1478 20: 3^20 mod 2047 = 340 21: 3^21 mod 2047 = 1020 22: 3^22 mod 2047 = 1013 23: 3^23 mod 2047 = 992 24: 3^24 mod 2047 = 929 25: 3^25 mod 2047 = 740 26: 3^26 mod 2047 = 173 27: 3^27 mod 2047 = 519 28: 3^28 mod 2047 = 1557 29: 3^29 mod 2047 = 577 30: 3^30 mod 2047 = 1731 31: 3^31 mod 2047 = 1099 32: 3^32 mod 2047 = 1250 33: 3^33 mod 2047 = 1703 34: 3^34 mod 2047 = 1015 35: 3^35 mod 2047 = 998 36: 3^36 mod 2047 = 947 37: 3^37 mod 2047 = 794 38: 3^38 mod 2047 = 335 39: 3^39 mod 2047 = 1005 40: 3^40 mod 2047 = 968 41: 3^41 mod 2047 = 857 42: 3^42 mod 2047 = 524 43: 3^43 mod 2047 = 1572 44: 3^44 mod 2047 = 622 45: 3^45 mod 2047 = 1866 46: 3^46 mod 2047 = 1504 47: 3^47 mod 2047 = 418 48: 3^48 mod 2047 = 1254 49: 3^49 mod 2047 = 1715 50: 3^50 mod 2047 = 1051 51: 3^51 mod 2047 = 1106 52: 3^52 mod 2047 = 1271 53: 3^53 mod 2047 = 1766 54: 3^54 mod 2047 = 1204 55: 3^55 mod 2047 = 1565 56: 3^56 mod 2047 = 601 57: 3^57 mod 2047 = 1803 58: 3^58 mod 2047 = 1315 59: 3^59 mod 2047 = 1898 60: 3^60 mod 2047 = 1600 61: 3^61 mod 2047 = 706 62: 3^62 mod 2047 = 71 63: 3^63 mod 2047 = 213 64: 3^64 mod 2047 = 639 65: 3^65 mod 2047 = 1917 66: 3^66 mod 2047 = 1657 67: 3^67 mod 2047 = 877 68: 3^68 mod 2047 = 584 69: 3^69 mod 2047 = 1752 70: 3^70 mod 2047 = 1162 71: 3^71 mod 2047 = 1439 72: 3^72 mod 2047 = 223 73: 3^73 mod 2047 = 669 74: 3^74 mod 2047 = 2007 75: 3^75 mod 2047 = 1927 76: 3^76 mod 2047 = 1687 77: 3^77 mod 2047 = 967 78: 3^78 mod 2047 = 854 79: 3^79 mod 2047 = 515 80: 3^80 mod 2047 = 1545 81: 3^81 mod 2047 = 541 82: 3^82 mod 2047 = 1623 83: 3^83 mod 2047 = 775 84: 3^84 mod 2047 = 278 85: 3^85 mod 2047 = 834 86: 3^86 mod 2047 = 455 87: 3^87 mod 2047 = 1365 88: 3^88 mod 2047 = 1 Now, again from what I have read (again, self taught and due to all of the greek symbols I am probably misinterpreting definitions and there is probably another correct definition as I doubt my own theories are anything yet undefined) Our ring is a commutative ring in that multiplication is commutative by addition, f(x+y)= f(x)*f(y) Ad 88 the ring repeats infinitely as 88 is a subgroup of G2047 and thus 89 divides 2047. Now when I speak of a number n, being an element of the ring, lets take MP-3 as f(1)=3 and 2047 XOR 3 = 2044 (Alternately we could say 2047-3) and 2044 SHOULD be symmetrically (I know this isn't the correct term) equivalent to 3, and hence should equal f(1024) where the symetrical element of x can be found at ((2^p/2)-1+x). And If MP11 where prime it would be. But since MP is not Prime f(1024)<>2044 but instead 3^1024 mod 2047 = 601. However in this type of ring let Y XOR MP = X and X XOR MP = Y, the XGCD(Y, MP)= -XGCD(X,MP) with x2^P/2 is not an element of G is to test 3^2^(P/2) MOD MP != MP-3. This essentially amounts to a Test for the Primality of MERSENNE NUMBERS with a slight faster run time than the Lucas, requiring no subtractions and one less step than the LUCAS. Now note that 3^MP mod MP does not necessarily have an order of MP-1 as required for a ring of prime p which requires the order to be P-1. For example, for MP13 G8191 has an order of 990 and an bit exponent interval of 280 for increments of f(x)*2. So when I say an number n is not an element of a ring, The following are elements of G[SUB2047][/sub] and no other numbers. 1 3^88 mod 2047 3 3^1 mod 2047 9 3^2 mod 2047 27 3^3 mod 2047 71 3^62 mod 2047 81 3^4 mod 2047 140 3^7 mod 2047 173 3^26 mod 2047 213 3^63 mod 2047 223 3^72 mod 2047 243 3^5 mod 2047 278 3^84 mod 2047 335 3^38 mod 2047 340 3^20 mod 2047 358 3^16 mod 2047 418 3^47 mod 2047 420 3^8 mod 2047 455 3^86 mod 2047 515 3^79 mod 2047 519 3^27 mod 2047 524 3^42 mod 2047 541 3^81 mod 2047 577 3^29 mod 2047 584 3^68 mod 2047 601 3^56 mod 2047 622 3^44 mod 2047 639 3^64 mod 2047 669 3^73 mod 2047 706 3^61 mod 2047 729 3^6 mod 2047 740 3^25 mod 2047 775 3^83 mod 2047 794 3^37 mod 2047 834 3^85 mod 2047 854 3^78 mod 2047 857 3^41 mod 2047 877 3^67 mod 2047 929 3^24 mod 2047 947 3^36 mod 2047 967 3^77 mod 2047 968 3^40 mod 2047 992 3^23 mod 2047 998 3^35 mod 2047 1005 3^39 mod 2047 1013 3^22 mod 2047 1015 3^34 mod 2047 1020 3^21 mod 2047 1051 3^50 mod 2047 1074 3^17 mod 2047 1099 3^31 mod 2047 1105 3^11 mod 2047 1106 3^51 mod 2047 1162 3^70 mod 2047 1175 3^18 mod 2047 1177 3^14 mod 2047 1204 3^54 mod 2047 1250 3^32 mod 2047 1254 3^48 mod 2047 1260 3^9 mod 2047 1268 3^12 mod 2047 1271 3^52 mod 2047 1315 3^58 mod 2047 1365 3^87 mod 2047 1439 3^71 mod 2047 1478 3^19 mod 2047 1484 3^15 mod 2047 1504 3^46 mod 2047 1545 3^80 mod 2047 1557 3^28 mod 2047 1565 3^55 mod 2047 1572 3^43 mod 2047 1600 3^60 mod 2047 1623 3^82 mod 2047 1657 3^66 mod 2047 1687 3^76 mod 2047 1703 3^33 mod 2047 1715 3^49 mod 2047 1731 3^30 mod 2047 1733 3^10 mod 2047 1752 3^69 mod 2047 1757 3^13 mod 2047 1766 3^53 mod 2047 1803 3^57 mod 2047 1866 3^45 mod 2047 1898 3^59 mod 2047 1917 3^65 mod 2047 1927 3^75 mod 2047 2007 3^74 mod 2047 Last fiddled with by alexhiggins732 on 2010-03-04 at 19:41   2010-03-04, 20:07 #11 alexhiggins732   Mar 2010 Brick, NJ 67 Posts Further Clarification I will also further clarify some of the terms I used above, since I know that they are "CrankSpeak" and hopefully the following will help in the translation to "PHDSpeak". Taking the traditional modular exponentiation algorithm and a Mersenne number as an exponent all bits are checked so there is no need to check if Exponent and 1 then, so we can simply right for I =0 to p-2. I'll start by pointing out my method for binary squaring mod MP which can be performed as followed: 14^2 mod 31; 3=14r2 and 11111r2 We take the bit rotations of the number to be squared 01110 11100 11001 10011 00111 and add the rotations for which the bits are checked 01110 : 0 11100 : 1 11001 : 1 10011 : 1 00111 : 0 --------- 1001000 = 72 mod 31 = 10 = 14^2 mod 31 While this method asymptotically slower than an FFT Power Mod, each step provides a great amount of information about the inner workings of the algorithm S^2 mod MP. For example <<1 is equivalent to *2 and leads to the discovery of what the exponential interval is between a number * 2. Here is a detailed print out for MP 13, noting that we define f(i) as ith iteration of a normal power mod and f(i, j) with j being each bit rotation. 13 mod 3 = 1; inverse=4 8191 mod 3 = 1; inverse=2730 THEOROM 1.1 If cycle length and Inverval can be found, modulus for any exponent can be calculated in super polynomial time simply by performing the correct chain of bit shifts. THEOROM 1.2 Given as cycle length L and an exponential interval e, the exact exponent that produces a given modulus can be calculated. Theorom 1.3 When MP is Prime: The cycle length is 2(LE), where LE is the exponenent whose residue = mP-1 for P=13, 8190 = 3^455 mod 8191 so cycle length=910 Further 8190/910=9 and exp interval=280 280=2*2*2*5*7 note that XGCD(3,8191)= 2730 and 2730 /3 = 910 for p=5, 30 = 3^15 mod 31 so cycle length=30 Further 30/30= 1 and ExpInterval=6 To Put it another way 3^(CycleLength/2) mod MP= MP-1 When MP is Not Prime: The Cycle Length LQ-1 where LQ is the largest divisor of MP In either case: Cycle Length +1 is a prime <- not tested (holds for MP5: 30+1, MP7: 990+1, MP11: 88+1) Exponent Interval +1 is prime.<- not tested (holds for MP5: 6+1, MP7: 280+1, MP11: ??) Theorom 1.4 Exponential interval is Power of 3 whose modulus = 2 Exp Base 2 Base 3 Base 6 280 128 2 256 <-- residue of base^exp mod 8091 Further if f(x)=2 then f(x+1)=6. we start out at 11 and first bit swap = 6 = 110 how to find? 2^(p-1)+1 * 2 mod MP=3 6*3=18=9*2 6*6=36=9*4 from xxx11 to 11xxx all= 3*2^n then 1xxx1 divisible by neither and finally back to xxx11 so 1xxx1^2 mod mp must = 3 MP5 2^4+1=17 2^(p-1) + 2^(p-2)*2 = 2^(p-1)+1 2^(p-1)+1 *2 mod MP=3 -> f(1,i) 1: 3^1 mod 31 = 3 0--> 0 += 3 = 3 --> f(1,0) = 00110 = 6 25: 3^25 mod 31 = 6 1--> 3 += 6 = 9 --> f(1,1) = 01100 = 12 19: 3^19 mod 31 = 12 --> f(1,2) = 11000 = 24 13: 3^13 mod 31 = 24 <=== note this actually mod 2 for mp5; for mp7 6144 = 3^351 mod 8191 --> f(1,3) = 10001 = 17 7: 3^7 mod 31 = 17 --> f(1,4) = 00011 = 3 1: 3^1 mod 31 = 3 ==================================== Exact Algorithm for Poly to be determined. Poly CycleLength=910 ExponentInverval=280 RatioCtoE=3.25 ==================================== NOTE: CYCLE LENGTH IS ACTUALLY 910 HERE. EXPONENTIAL INTERVAL BETWEEN POWERS OF 2 IS 280 In Reverse order 1-280=-279+910=631 = f(1,11) 631-280=351 = f(1,10) 351-280=71 = f(1, 9) 71-280=-209+910=701 = f(1, 8) 710-280=421 = f(1, 7) 421-280=141 = f(1, 6) 141-280=-139+910=771 = f(1, 5) 771-280=491 = f(1, 4) 491-280=211 = f(1, 3) 211-280=-69+910=841 = f(1, 2) 841-280=561 = f(1, 1) 561-280=281 = f(1, 0) In Order f(1) = 3 = 3^ 1 f(1,0) = 6 = 3^ 281 = 1 + 280 f(1,1) = 12 = 3^ 561 = 281 + 280 f(1,2) = 24 = 3^ 841 = 561 + 280 f(1,3) = 48 = 3^ 211 = 841 + 280 = 1121 mod 910 f(1,4) = 96 = 3^ 491 = 211 + 280 f(1,5) = 192 = 3^ 771 = 491 + 280 f(1,6) = 384 = 3^ 141 = 771 + 280 = 1051 mod 910 f(1,7) = 768 = 3^ 421 = 141 + 280 f(1,8) = 1536 = 3^ 701 = 421 + 280 f(1,9) = 3072 = 3^ 71 = 710 + 280 = 990 mod 910 f(1,10) = 6144 = 3^ 351 = 71 + 280 f(1,11) = 4097 = 3^ 631 = 351 + 280 f(1,12) = 3 = 3^ 1 = 631 + 280 = 911 mod 910 Last fiddled with by alexhiggins732 on 2010-03-04 at 20:10 Reason: Typo   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post king Information & Answers 1 2018-03-05 05:52 alpertron Miscellaneous Math 17 2012-04-30 15:28 CRGreathouse Math 4 2009-03-12 16:00 JuanTutors Math 3 2004-08-01 19:07 schneelocke PrimeNet 6 2003-11-22 01:26

All times are UTC. The time now is 19:41.

Wed Dec 1 19:41:50 UTC 2021 up 131 days, 14:10, 1 user, load averages: 1.47, 1.52, 1.50