mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2021-06-10, 00:44   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32·41 Posts
Default how do I find a and b with a²+b²=1 mod f

A peaceful and pleasant night for you,

how do I find (fast ?) a gaussian number a+bi with a²+b²=1 mod f
where f is an odd number.

Perhaps this question might be interesting also for others.

A link or some keywords would be helpful.



Last fiddled with by bhelmes on 2021-06-10 at 00:45
bhelmes is offline   Reply With Quote
Old 2021-06-10, 01:05   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

27578 Posts
Default

a+b*I=1 looks like good for every f.
R. Gerbicz is offline   Reply With Quote
Old 2021-06-10, 09:07   #3
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

2C216 Posts
Default

Well, you know Pythagorean triples, right? They satisfy a2 + b2 = c2. When both sides are divided by c2, we are left with (a/c)
2 + (b/c)2 = 1. So the rational points on the circle described by x2 + y2 = 1 are simply reduced Pythagorean triples. Thus for any Pythagorean triple (you can find a quick formula for them on Wikipedia) you reduce it and find one such point in the plane. You can extend these points infinitely far, by setting the right-hand side of the equation to k*f + 1, say f is 3, and k is 2, then the number is 7, and multiplying the coordinates of the point on the unit circle by the square root of the number.

For example:

3,4,5 - Smallest Pythagorean triple
(3/5)2 + (4/5)2 = 1
(sqrt(7)*3/5)2 + (sqrt(7)*4/5)2 = 1 (mod 3)

There are other points on the unit circle, obviously, but those are irrational, so not as easy to find them all as rational points. But, you can extend any one of them (both the rational and irrational) by this method.

So for given modulo f, you get the set of circles (sqrt(k*f+1)*x)2 + (sqrt(k*f+1)*y)2 = 1 (mod k*f+1), for k from 0 to inf.

Finding a point on a unit circle is thus a pretty easy task, I think. You can basically brute force it: Choose any real number between 0 and 1, find its other coordinate on respective point on the unit circle, and extend to infinity and beyond.
Viliam Furik is offline   Reply With Quote
Old 2021-06-10, 12:43   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

140D16 Posts
Default

Quote:
Originally Posted by bhelmes View Post
A peaceful and pleasant night for you,

how do I find (fast ?) a gaussian number a+bi with a²+b²=1 mod f
where f is an odd number.
<snip>
As already observed, taking a^2 and b^2 congruent to 0 and 1 (mod f) is always a solution. Thus [0, 1] or [0, f-1] always work.

If f has more than one prime factor, there will be other solutions to y^2 == 1 (mod f), giving other solutions where one of a and b is 0 (mod f).

Assuming you want 0 < a < f, 0 < b < f, you are out of luck if f = 3 or 5.

If f > 5, one way might be to find some prime p congruent to 1 (mod 4) which does not divide f. [This should not take very long if you just try them in increasing order - 5, 13, 17, 29, 37,... .]

Let [c, d] = qfbsolve(Qfb(1,0,1),p)

Compute e = znorder(Mod(p,f)). Then p^e is congruent to 1 (mod f), and

a + b*I = (c + d*I)^e. [This could be done mod f, and the results lifted to give a and b-values less than f if desired. If one of these reduces to 0 (mod f), try again.]

Another possibility is to find a prime p congruent to 1 (mod 4*f).

Then qfbsolve((Qfb(1,0,1),p) gives a solution. This could be reduced mod f if desired. If one of them is 0 (mod f), try again.

However, I don't know how quickly one might find such a prime p.

I have no idea how many tries might be required for either method to assure success, but I am pretty sure that for odd f > 3 there are solutions to x^2 + y^2 == 1 (mod f) with Mod(x,f) and Mod(y,f) both nonzero.

Last fiddled with by Dr Sardonicus on 2021-06-10 at 22:19 Reason: Insert omitted case
Dr Sardonicus is offline   Reply With Quote
Old 2021-06-11, 02:32   #5
bhelmes
 
bhelmes's Avatar
 
Mar 2016

32·41 Posts
Default

Thanks a lot for all replies.

Is this a mathematical correct way:

1. Choose a,b with a>0 and b>0 and a=/=b and a²+b² =/=0 mod f
(the trivial solutions are not important for me)

2. Set tan (alpha)=a/b

3. Double the angle with tan(2*alpha)=2/[cot(alpha) - tan (alpha)] = A/B

4. then sin (2*alpha)=A/(a²+b²) and cos (2*alpha)=B/(a²+b²)

5. Calculate a'= A*(a²+b²)⁻¹ mod f and b'=B*(a²+b²)⁻¹ mod f

6. (a')² + (b')²=1 mod f


Correct ?


bhelmes is offline   Reply With Quote
Old 2021-06-12, 15:03   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×29×59 Posts
Default

Quote:
Originally Posted by bhelmes View Post
Thanks a lot for all replies.

Is this a mathematical correct way:

1. Choose a,b with a>0 and b>0 and a=/=b and a²+b² =/=0 mod f
(the trivial solutions are not important for me)

2. Set tan (alpha)=a/b

3. Double the angle with tan(2*alpha)=2/[cot(alpha) - tan (alpha)] = A/B

4. then sin (2*alpha)=A/(a²+b²) and cos (2*alpha)=B/(a²+b²)

5. Calculate a'= A*(a²+b²)⁻¹ mod f and b'=B*(a²+b²)⁻¹ mod f

6. (a')² + (b')²=1 mod f


Correct ?
No.

In (1), a^2 + b^2 =/= 0 (mod f) is not sufficient to insure that a^2 + b^2 has a multiplicative inverse (mod f).

I leave the determination of the appropriate condition as an exercise.

Assuming a^2 + b^2 has a multiplicative inverse (mod f), then

(2*a*b*(a^2 + b^2)^(-1))^2 + ((b^2 - a^2)*(a^2 + b^2)^(-1))^2 == 1 (mod f)

is valid.

If the a and b you have chosen do not satisfy the condition, you need to keep trying until you find a pair that does.
Dr Sardonicus is offline   Reply With Quote
Old 2021-06-13, 08:51   #7
0scar
 
Jan 2020

22×32 Posts
Default

Quote:
Originally Posted by bhelmes View Post

Correct ?
With your "trigonometric" approach, you use integer parameters a and b to build a Pythagorean triplet A,B,C:
A = 2*a*b,
B = b^2 - a^2,
C = a^2 + b^2.
Then you generate a candidate solution:
x = A*(C^-1) mod f,
y = B*(C^-1) mod f,
where, like Dr. Sardonicus, I understand the operation "C^-1" as computing the multiplicative inverse of C modulo f, which exists if and only if C is coprime with f.
In order to emphasize this dependency from f, I'll write it as "modinv(C,f)".
You also ask to avoid "trivial" solutions; let's define a solution (x,y) "trivial" if x^2 == 0 mod f and y^2 == 1 mod f, or if y^2 == 0 mod f and x^2 == 1 mod f.

What about the conditions you gave at point (1)?
For a given odd integer f, a "legal" starting choice (a,b) may fail to generate a solution:
f = 25, a = 1, b = 3, C = 10,
modinv(10,25) doesn't exist
Or it may generate an unwanted trivial solution:
f = 7, a = 3, b = 4, C = 25,
modinv(25,7) = 2,
x = 24*2 = 48 == 6 mod 7
y = 7*2 = 14 == 0 mod 7

But, if f is coprime with 15, your "Pythagorean" construction provides a non-trivial solution at the very first choice a = 1, b = 2:
x = 4*modinv(5,f)
y = 3*modinv(5,f)
We can easily see that it's non-trivial because the eight numbers 3, 4, 5, modinv(5,f), x, y, x^2, y^2 are all coprime with f.
Example with f = 7:
modinv(5,7) = 3
x = 4*3 = 12 == 5 mod 7
y = 3*3 = 9 == 2 mod 7
5^2+2^2 = 29 == 1 mod 7

Now suppose that f is not coprime with 15, but it has at least two distinct prime divisors, so that we can "factor" f as g*h, with gcd(g,h) = 1.
Let's try another kind of construction.
By chinese remainder theorem, the following system of congruences is solvable:
x == 0 mod g
x == 1 mod h
y == 1 mod g
y == 0 mod h
We can see that we get a non-trivial solution because:
congruence x^2+y^2 == 1 holds modulo g and modulo h, so also modulo g*h
congruence x^2 == 0 holds modulo g but not modulo h, so not modulo g*h
congruence y^2 == 0 holds modulo h but not modulo g, so not modulo g*h
Example with f=15, g=3, h=5:
x == 0 mod 3 and x == 1 mod 5, so x == 6 mod 15
y == 1 mod 3 and y == 0 mod 5, so y == 10 mod 15
6^2+10^2 = 136 == 1 mod 15

Together, the "Pythagorean" and "Chinese" constructions cover all odd numbers f, excluding the prime powers of the form f=3^n or f=5^n.
For these cases, we can use Hensel lifting.
Given a solution (x,y) for f = p^n, we can build a solution (x,y') for f' = p^(n+1) as follows.
Consider the quadratic congruence:
x^2 + y'^2 == 1 mod p^(n+1)
after the substitutions:
y' = y + R*p^n
x^2 + y^2 = 1 + Q*p^n
and some simplifications, we obtain the linear congruence:
Q + 2*y*R == 0 mod p
which can be easily solved:
R == -Q*modinv(2*y,p) mod p

Example: prime powers of the form 3^n.
for n = 1, two solutions, all trivial: (0,1) (0,2)
for n = 2, six solutions, all trivial: (0,1) (0,8) (3,1) (3,8) (6,1) (6,8)
for n = 3, twelve non-trivial solutions, including (3,10) and (3,17)
Lifting only them, we obtain:
for n=4, solutions (3,37) and (3,44)
for n=5, solutions (3,199) and (3,44)
and so on.
0scar is offline   Reply With Quote
Old 2021-06-15, 00:30   #8
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

96510 Posts
Default

Hi again,

Four solutions that come to mind are { 1, -1, i, and -i}

not a complete set.

Matt
MattcAnderson is offline   Reply With Quote
Old 2021-06-15, 13:01   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

140D16 Posts
Default

If f = q, a prime number, the number of solutions to x^2 + y^2 = 1 (mod q) may be counted as follows:

Note that 1 + (a/q) or 1 + kronecker(a,q) is 2 if a is a quadratic residue (mod q), 0 if a is a quadratic non-residue (mod q), and 1 if a == 0 (mod q). Then

(1 + (r/q))*(1 + ((1-r)/q)) =
  • 4, if r and 1 - r are both quadratic residues (mod q)
  • 0, if either r or 1 - r is a quadratic non-residue (mod q), and
  • 2 if {r, 1 - r} = {0 mod q, 1 mod q}

Thus we get a contribution of 4 for each non-trivial solution, and a contribution of 2 for each of (r, 1 - ) = (0,1) and (1, 0). Now

(1 + (r/q))*(1 + ((1-r)/q)) = 1 + (r/q) + ((1 - r)/q) + (r*(1-r)/q)

Let n be the number of non-trivial solutions. Summing on all r (mod q) we have

4*n + 4 = q + 0 + 0 + J(\chi,\chi)

where J is a Jacobi sum, and \chi is the quadratic character (a/q). Since this character is self-inverse, the Jacobi sum evaluates to -(-1/q). Thus

4*n + 4 = q -(-1/q), or

n = (q - (-1/q))/4 - 1.

This formula gives n = 0 for q = 3 or 5, but n > 0 for q > 5.

EDIT: Pursuant to a PM from a discerning reader, I have changed the name of the arbitrary residue (mod q) from "a" to r. My previous usage of "a" was confusing since it is used in the subject to denote a root of one of the squares.

The above formula counts the number of pairs of squares (a^2, b^2) (mod q) for which a^2 + b^2 == 1 (mod q). Determining the corresponding number of distinct pairs (a, b) is a bit involved.

For any pair of roots (a, b) we can, by replacing a by q - a or b with q - b if necessary, and reordering the pair if necessary, assume that 0 <= a <= b < q/2. By changing signs and reordering this pair, we can nominally produce eight "equivalent" pairs. But if a = 0 or a = b, that number goes down. I'm too lazy to work out the details.

Last fiddled with by Dr Sardonicus on 2021-06-21 at 12:36 Reason: missing equals sign; awkward phrasing; add clarification
Dr Sardonicus is offline   Reply With Quote
Old 2021-06-17, 13:19   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

140D16 Posts
Default

Let f > 1 be an odd integer. The set of Gaussian integers mod f,

Mod(a,f) + Mod(b,f)*I

for which

Mod(a^2 + b^2, f) = Mod(1, f)

forms a subgroup of the multiplicative group (Z[I]/f)* of invertible elements of Z[I]/f .

Taking a prime p == 1 (mod 4) which does not divide f, and x^2 + y^2 = p, we have that Mod(x^2 + y^2, f) is invertible, so that the "trigonometric solution" is valid:

a = Mod(2*x*y/(x^2 + y^2), f), b = Mod((x^2 - y^2)/(x^2 + y^2), f).

I note that for f > 5, the smallest p satisfies p < f, so that a and b are both nonzero residues (mod f) [however, for f = 9 or 25, a^2 or b^2 is 0 (mod f)].

By replacing a by f - a or b with f - b if necessary, we can assume that 0 < a < f/2 and 0 < b < f/2.

The smallest f > 5 requiring p > 5 is f = 15, as do f = 15 + 10*k; the smallest f requiring p > 13 is f = 5*13 = 65, as do f = 5*13 + 10*13*k; the smallest f requiring p > 17 is f = 5*13*17, as do 5*13*17 + 10*13*17*k, and so on.

For f = 27, taking the "trigonometric solution" using p = 5 gives a = Mod(44, 27), b = Mod(33, 27) which give a = 17, b = 6. One can take a = 27 - 17 = 10 < 27/2; 10^2 + 6^2 = 136 = 27*5 + 1

For f = 125, p = 13 gives a = Mod(924,125) and b = Mod(385, 125) or a = 49, b = 10; 49^2 + 10^2 = 2501 = 125* 20 + 1.
Dr Sardonicus is offline   Reply With Quote
Old 2021-06-20, 00:24   #11
bhelmes
 
bhelmes's Avatar
 
Mar 2016

17116 Posts
Default

A peaceful and pleasant night for you,

For people who like php-scripts I added a calculator which decline from the pyth. trippel to the gaussian integer modulo f:

http://devalco.de/System/system_one_complex_pyth2.php

I noticed that this transformation is surjectiv.


bhelmes is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where can I find a Reverse and Add program? I can't find any! Stargate38 Programming 18 2015-07-10 06:08
Find the Value davar55 Puzzles 7 2009-07-02 19:46
Find the Value davar55 Puzzles 25 2007-07-15 15:56
New way to Find (X^Y) % M maheshexp Miscellaneous Math 29 2004-08-30 15:59
New way to Find (X^Y) % M maheshexp Software 2 2004-05-08 03:16

All times are UTC. The time now is 11:28.


Sun Dec 5 11:28:31 UTC 2021 up 135 days, 5:57, 0 users, load averages: 1.42, 1.29, 1.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.