20200822, 16:25  #1 
Jun 2019
2·17 Posts 
x³=8 MOD n
LET n prime numbre and n = 1 mod 3
Code:
n=1618033988749894848204586834365638117720309179805762862135448622705260462818902449707207204189391137484754088075386891752126633862223536931793180060766726354433389086595939582905638322661319928290267880675208766892501711696207032221043216269548626296313614438149758701220340805887 2^{3}=8 MOD n I developed a program that can calculate x^{3}= 8 mod n and x ≠ 2 Code:
x = 2171711333883339670941324495281023746596543610935753324951505220702238424082536822013428825631640608333554143771151354569412145305946444029063176869427472712892146427824846336952101729852264280249432279000433641133160067502051398856719583078834374067152741148195787768110600411990 for 3^{3}=27 MOD n Code:
x= 3214568954174569886406360594541016850986421302819421461114536659767684215151804565808685578310103637438685136644820535154388317489974481683577954938925696348395336704646488826194400695866883292786923104200184605870266745531751030599093490459942944084525346030305353152715462605560 Last fiddled with by retina on 20200822 at 22:47 Reason: Fix exponent in title 
20200822, 18:53  #3  
Jun 2019
2×17 Posts 
Quote:
i use pari gp and i compare factor(x^3Mod(8,((n))) vs my method (have speed at all) but my method work only if n mod 4 = 3 because i use y^{(n+1)/4}mod n to find the cubic roots 

20200822, 19:31  #4 
Jun 2019
2·17 Posts 
this code in (python)
def r(a,n,u): c2=(n*u)a j= (c2//2) j22=pow(int(j),2,n) t=pow(c2,2,n) dif=j22t z=pow(dif,int((n+1)//4),n) k=(c2+(z*2))//2 print(k) example a = 2 n= 31 u= 1 or 2 or 3 ferst test r(2,31,1) result 19 success Last fiddled with by baih on 20200822 at 20:29 
20200823, 03:58  #5  
Aug 2006
2^{2}×1,483 Posts 
Quote:


20200823, 05:23  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}×7×163 Posts 
I didn't want to upset him :)
(and he didn't reveal what he was doing until later. I wanted to get him to open up... and I did. For my little project a few years ago I took cube roots of 2 for sieving near cube primes f(x)^3+2 ad nauseum for all sorts of p, not just 1(mod 6), so I knew that even that is not so hard in the most general case.) 
20200823, 13:48  #7 
Feb 2017
Nowhere
110111111001_{2} Posts 
It is well known (and has been pointed out in the Forum in times past) that when p == 3 (mod 4), extracting a square root of a quadratic residue is easily done with an integer powmod.
So, finding a square root of 3 (mod p) for p == 1 (mod 3) is easy for p == 7 (mod 12) but not for p == 1 (mod 12). In what follows, I will assume that r is not the cube of an integer. For p == 1 (mod 3), there is the (hopefully) obvious criterion that a nonzero residue r is a cubic residue (mod p) if and only if Mod(r,p)^((p1)/3) = Mod(1, p). For r = 2, we have the classical result that 2 is a cubic residue when p = A^{2} + 3*B^{2} with B divisible by 3. For example, 2^{10} == 1 (mod 31) (as is infinitely well known, 2^{5}  1 = 31) and 2^{2} + 3*3^{2} = 31. Generically, the cubic x^{3}  r (mod p) will split into linear factors for about 1/3 of primes p == 1 (mod 3). Unfortunately, which third of primes can not be determined by rational congruence criteria. Note that, for p == 1 (mod 3), 3 always has a square root (mod p), so the equation x^{2} + x + 1 = 0 is always solvable (mod p). Thus, if the cubic has one linear factor it automatically splits completely into linear factors. Therefore, x^{3}  r will either split completely into linear factors or be irreducible for p == 1 (mod 3). If it splits, the ratio of any two of the roots will give a cube root of 1 (mod p). If one wants to determine the cube roots of r when r is a cubic residue (mod p) for a large number of p's (all congruent to 1 mod 3), and also assuming that nothing is known about the p's (or r) that would influence whether r is a cubic residue, I'm guessing that, rather than doing the factormod for every p, it would be faster to first test whether Mod(r,p)^((p1)/3) = Mod(1, p); if p "fails" the test, move on to the next p; but if p "passes" the test, do factormod(x^3  r, p). I'm assuming the integer powmod is significantly faster than the factormod, and checking with it first will avoid doing the factormod for 2/3 of the p's. Once upon a time, Phil Carmody asked me about using cubic reciprocity in conjunction with sieving while looking for primes of the form X^{2} + X + 1. After screwing it up once, I fixed my mistake and Phil implemented the criterion. IIRC he liked it, but finally concluded that it really didn't make the computations go any faster. 
20200823, 18:20  #8 
Aug 2006
2^{2}·1,483 Posts 

20200824, 01:04  #9  
Jun 2019
2·17 Posts 
Quote:
LET a^{3}= b mod n x^{3}= b mod n y^{3}= b mod n na = x+y we have x+y and we want xy to find x the key is (x+y)^{2} mod n = xy mod n if a^{3}= b mod n x^{3}= b mod n y^{3}= b mod n then to find x or y we know that xy = u1^{2}  u2^{2} and easy to calculate u1 by x+y u1^{2} mod n  ( x+y)^{2} mod n = f reverse f to find xy = 2 ( f ^{(n+1)/4} mod n ) this code in (python) def r(a,n,u): c2=(n*u)a j= (c2//2) j22=pow(int(j),2,n) t=pow(c2,2,n) dif=j22t z=pow(dif,int((n+1)//4),n) k=(c2+(z*2))//2 print(k) example a = 2 n= 31 u= 1 or 2 or 3 ferst test r(2,31,1) result 19 success 

20200831, 23:01  #10 
"Sam"
Nov 2016
474_{8} Posts 
The thread discussion raises an interesting problem I had in mind:
For primes q and (odd) p How does one find solutions to x^q = a mod p given that p = 1 mod q^2 provided the solutions exist and gcd(a,p)=1? With q = 2 and p = 3 mod 4, the solutions to x^2 = a mod q, one solution is recovered from x = a^((p+1)/4) mod p The other solution is x. This works because a^((p + 1)/2) = a mod p, and since p = 3 mod 4, (p  1)/2 is odd, therefore (p  1)/2 + 2 = (p + 1)/2 is even, so we can easily take a square root of a mod p. When q is odd and p ≠ 1 mod q^2, a solution to x^q = a mod p can be obtained as follows: Let d = (p  1)/q. a^d = 1 mod p As d ≠ 0 mod q, by the Chinese Remainder Theorem we have an integer k < q such that k*d+1 = 0 mod q. Then a^(k*d) = 1 mod p a^(k*d+1) = a mod p a^((k*d+1)/q) = x mod p. Thus x^q = a mod p, the rest of the solutions are obtained by multiplying x by the qth roots of unity mod p. Note that if p = 1 mod q^2, then d = 0 mod q, and thus k*d+1 = 0 mod q is impossible, so a solution cannot be found this way. With q = 2, the quadratic solution case, Cipolla's algorithm works for all p, not just those congruent to 3 mod 4. Is there something similar for qth power reciprocity when p = 1 mod q^2? Last fiddled with by carpetpool on 20200831 at 23:01 
20200901, 11:59  #11 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1612_{8} Posts 
I found the paper by Padró and Sáez (2002) (paper) to work well for cube roots. It shows an explicit modification to TonelliShanks. My implementation worked without trouble.
There are really easy solutions for p = 2 mod 3, p = 4 mod 9, and p = 7 mod 9, where a single powmod and you're done. For generic roots it's harder, and for composites as well. Pari/GP doesn't handle composite moduli using Mod(a,n) though does with padic. Slightly troubling is that with the former it usually silently returns the wrong answer, though the documentation does say it is only for primes. I tried implementing AMM from both Holt (2003) and Cao/Sha/Fan (2011) with no success (that is, it wouldn't work on 100% of inputs, and I couldn't determine why). In theory AMM should handle both prime and prime power moduli. This isn't a fault of the algorithm, but noting that something there seemed obvious to the authors that wasn't clear to me. I first tried real simple stuff  for primes use a gcd and for composites use Lindhurst (1997) proposition 3 to reduce the root (k) to what isn't covered by a trivial inverse+powmod, then for either primes or composites do znprimroot, znlog, then a powmod. That's great except it's a bit expensive and one can't always get a primitive root. I eventually threw all that plus the cube root stuff away and implemented van de Woestijne (2006) (paper) Algorithms 2.1 (to reduce k to just the nontrivial part), and 3.3 (generalized TonelliShanks). As far as I can tell, this is essentially what Pari/GP implements, though being a generalized TonelliShanks it could easily be completely independent. For prime modulus it works very well and doesn't have an issue some of the other methods gave me, where you get a root for, e.g. k=3 then raise to k=9, then find that it doesn't have a solution for k=27 and now you're kind of stuck. (in this case there *is* a solution for k=27, but not from the root we got at k=9). For composites it was a bit trickier since I did want it to work. Split the modulus n into p^k etc. and solve each one, then CRT. Works great except p^k where k > 2 sometimes fails to Hensel lift. I included a bit of backtracking for the cases that don't lift. There is probably a clever solution here that just solves this correctly without any stupid searching for the right root. Anyway, with a correct solution for each root mod p^k, they all combine just fine with CRT. At some point I'll look into the Johnston (1999) algorithm as used in SAGE and SymEngine. The paper is hidden behind paywalls so I haven't been able to read the paper (I've had an ACM DL subscription for years, but let it lapse this year since I have no income). It doesn't look particularly involved from looking at the source of those implementations. Last fiddled with by danaj on 20200901 at 12:17 Reason: generic > generalized 