x³=8 MOD n

[baih]

LET n prime numbre and n = 1 mod 3

n=1618033988749894848204586834365638117720309179805762862135448622705260462818902449707207204189391137484754088075386891752126633862223536931793180060766726354433389086595939582905638322661319928290267880675208766892501711696207032221043216269548626296313614438149758701220340805887

2³=8 MOD n

I developed a program that can calculate x³= 8 mod n and x ≠ 2

x = 2171711333883339670941324495281023746596543610935753324951505220702238424082536822013428825631640608333554143771151354569412145305946444029063176869427472712892146427824846336952101729852264280249432279000433641133160067502051398856719583078834374067152741148195787768110600411990

for 3³=27 MOD n

x=
3214568954174569886406360594541016850986421302819421461114536659767684215151804565808685578310103637438685136644820535154388317489974481683577954938925696348395336704646488826194400695866883292786923104200184605870266745531751030599093490459942944084525346030305353152715462605560

[Batalov]

Well-known methods exist for taking modular cubic roots.
Here, on this forum you can find how.

What is your method's differences from known methods?

[baih]

Originally Posted by Batalov

Well-known methods exist for taking modular cubic roots.
Here, on this forum you can find how.

What is your method's differences from known methods?

THANKS
i use pari gp and i compare

factor(x^3-Mod(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)/4mod n to find the cubic roots

[baih]

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=j22-t

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

[CRGreathouse]

Originally Posted by Batalov

Well-known methods exist for taking modular cubic roots.
Here, on this forum you can find how.

What is your method's differences from known methods?

Well, except here the poster is really finding a square root, not a cube root -- a modular root of x^2 + 2x + 4. Specifically, the roots are -1 ± sqrt(-3) mod n.

[Batalov]

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

[Dr Sardonicus]

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)^((p-1)/3) = Mod(1, p).

For r = 2, we have the classical result that 2 is a cubic residue when p = A² + 3*B² with B divisible by 3.

For example, 2¹⁰ == 1 (mod 31) (as is infinitely well known, 2⁵ - 1 = 31) and 2² + 3*3² = 31.

Generically, the cubic x³ - 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² + 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³ - 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)^((p-1)/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² + 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.

[CRGreathouse]

Originally Posted by Batalov

I wanted to get him to open up... and I did.

I bow to your superior mastery of soft skills.

[baih]

Originally Posted by Batalov

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

LET
a³= b mod n
x³= b mod n
y³= b mod n

n-a = x+y we have x+y and we want x-y to find x

the key is (x+y)² mod n = xy mod n if

a³= b mod n
x³= b mod n
y³= b mod n


then to find x or y

we know that xy = u1² - u2²

and easy to calculate u1 by x+y



u1² mod n - ( x+y)² mod n = f


reverse f to find
x-y = 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=j22-t

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

[carpetpool]

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 q-th 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 q-th power reciprocity when p = 1 mod q^2?

[danaj]

I found the paper by Padró and Sáez (2002) (paper) to work well for cube roots. It shows an explicit modification to Tonelli-Shanks. 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 p-adic. 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 non-trivial part), and 3.3 (generalized Tonelli-Shanks). As far as I can tell, this is essentially what Pari/GP implements, though being a generalized Tonelli-Shanks 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.