 mersenneforum.org > Math how do I find a and b with a²+b²=1 mod f
 Register FAQ Search Today's Posts Mark Forums Read 2021-06-10, 00:44 #1 bhelmes   Mar 2016 32·41 Posts 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   2021-06-10, 01:05 #2 R. Gerbicz   "Robert Gerbicz" Oct 2005 Hungary 27578 Posts a+b*I=1 looks like good for every f.   2021-06-10, 09:07 #3 Viliam Furik   "Viliam Furík" Jul 2018 Martin, Slovakia 2C216 Posts 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.   2021-06-10, 12:43   #4
Dr Sardonicus

Feb 2017
Nowhere

140D16 Posts Quote:
 Originally Posted by bhelmes 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.
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   2021-06-11, 02:32 #5 bhelmes   Mar 2016 32·41 Posts 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 ?      2021-06-12, 15:03   #6
Dr Sardonicus

Feb 2017
Nowhere

3×29×59 Posts Quote:
 Originally Posted by bhelmes 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.   2021-06-13, 08:51   #7
0scar

Jan 2020

22×32 Posts Quote:
 Originally Posted by bhelmes 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.
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.   2021-06-15, 00:30 #8 MattcAnderson   "Matthew Anderson" Dec 2010 Oregon, USA 96510 Posts Hi again, Four solutions that come to mind are { 1, -1, i, and -i} not a complete set. Matt   2021-06-15, 13:01 #9 Dr Sardonicus   Feb 2017 Nowhere 140D16 Posts 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 + where J is a Jacobi sum, and 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   2021-06-17, 13:19 #10 Dr Sardonicus   Feb 2017 Nowhere 140D16 Posts 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.   2021-06-20, 00:24 #11 bhelmes   Mar 2016 17116 Posts 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.     Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Programming 18 2015-07-10 06:08 davar55 Puzzles 7 2009-07-02 19:46 davar55 Puzzles 25 2007-07-15 15:56 maheshexp Miscellaneous Math 29 2004-08-30 15:59 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