mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-08-22, 16:25   #1
baih
 
baih's Avatar
 
Jun 2019

2·17 Posts
Default x³=8 MOD n

LET n prime numbre and n = 1 mod 3


Code:
n=1618033988749894848204586834365638117720309179805762862135448622705260462818902449707207204189391137484754088075386891752126633862223536931793180060766726354433389086595939582905638322661319928290267880675208766892501711696207032221043216269548626296313614438149758701220340805887

23=8 MOD n

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


Code:
x = 2171711333883339670941324495281023746596543610935753324951505220702238424082536822013428825631640608333554143771151354569412145305946444029063176869427472712892146427824846336952101729852264280249432279000433641133160067502051398856719583078834374067152741148195787768110600411990

for 33=27 MOD n




Code:
x=
3214568954174569886406360594541016850986421302819421461114536659767684215151804565808685578310103637438685136644820535154388317489974481683577954938925696348395336704646488826194400695866883292786923104200184605870266745531751030599093490459942944084525346030305353152715462605560

Last fiddled with by retina on 2020-08-22 at 22:47 Reason: Fix exponent in title
baih is offline   Reply With Quote
Old 2020-08-22, 16:52   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×7×163 Posts
Default

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?
Batalov is offline   Reply With Quote
Old 2020-08-22, 18:53   #3
baih
 
baih's Avatar
 
Jun 2019

2×17 Posts
Default

Quote:
Originally Posted by Batalov View Post
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 is offline   Reply With Quote
Old 2020-08-22, 19:31   #4
baih
 
baih's Avatar
 
Jun 2019

2·17 Posts
Default

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

Last fiddled with by baih on 2020-08-22 at 20:29
baih is offline   Reply With Quote
Old 2020-08-23, 03:58   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×1,483 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2020-08-23, 05:23   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×7×163 Posts
Cool

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.)
Batalov is offline   Reply With Quote
Old 2020-08-23, 13:48   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

1101111110012 Posts
Default

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 = A2 + 3*B2 with B divisible by 3.

For example, 210 == 1 (mod 31) (as is infinitely well known, 25 - 1 = 31) and 22 + 3*32 = 31.

Generically, the cubic x3 - 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 x2 + x + 1 = 0 is always solvable (mod p). Thus, if the cubic has one linear factor it automatically splits completely into linear factors. Therefore, x3 - 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 X2 + 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.
Dr Sardonicus is offline   Reply With Quote
Old 2020-08-23, 18:20   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22·1,483 Posts
Default

Quote:
Originally Posted by Batalov View Post
I wanted to get him to open up... and I did.
I bow to your superior mastery of soft skills.
CRGreathouse is offline   Reply With Quote
Old 2020-08-24, 01:04   #9
baih
 
baih's Avatar
 
Jun 2019

2·17 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
a3= b mod n
x3= b mod n
y3= b mod n

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

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

a3= b mod n
x3= b mod n
y3= b mod n


then to find x or y

we know that xy = u12 - u22

and easy to calculate u1 by x+y



u12 mod n - ( x+y)2 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
baih is offline   Reply With Quote
Old 2020-08-31, 23:01   #10
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

4748 Posts
Post

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?

Last fiddled with by carpetpool on 2020-08-31 at 23:01
carpetpool is offline   Reply With Quote
Old 2020-09-01, 11:59   #11
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

16128 Posts
Default

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.

Last fiddled with by danaj on 2020-09-01 at 12:17 Reason: generic -> generalized
danaj is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 05:32.

Wed Oct 28 05:32:07 UTC 2020 up 48 days, 2:43, 2 users, load averages: 1.61, 1.74, 1.66

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.