Residue identification algorithm

[SPWorley]

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?

[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)).

[SPWorley]

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)).

Thanks for the quick reply!

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?

[maxal]

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

[maxal]

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.

[SPWorley]

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.

[SPWorley]

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

[alexhiggins732]

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.

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.

[R.D. Silverman]

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.

[alexhiggins732]

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 G₂₀₄₇ 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 G₂₀₄₇ 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 x<y<mp which allows Y (in the above example 2044) LIE about being an element of G_MP.

However, the only way (that I have so far discovered) to tell whether an element >2^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 G₈₁₉₁ 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

[alexhiggins732]

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=14_r2 and 11111_r2
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 i^th 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