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, 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

 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