Tonelli-Shanks algorithm: Difference between revisions

 

 

 

It is used in [https://en.wikipedia.org/wiki/Rabin_cryptosystem cryptography] techniques.

 

 

 

 

 

 

 

 

;Task:

 

Find solutions (if any) for

* n = 1032 p = 10009

* n = 44402 p = 100049

 

;Extra credit:

* [[Cipolla's algorithm]]

<br><br>

 

=={{header|D}}==

{{trans|Kotlin}}

import std.stdio;

import std.typecons;

}

else writeln("No solution exists");

 

{{out}}

 

=={{header|EchoLisp}}==

(require 'bigint)

;; test equality mod p

(mod:≡ t (* t c) p)

(set! m i)))))

{{out}}

<pre>

❌ error: not a square (mod p) (1032 10009)

</pre>

=={{header|FreeBASIC}}==

===LongInt version===

' compile with: fbc -s console

' maximum for p is 17 digits to be on the save side

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>Find solution for n = 10 and p = 13

===GMP version===

{{libheader|GMP}}

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>Find solution for n = 10 and p = 13

===int===

Implementation following Wikipedia, using similar variable names, and using the int type for simplicity.

 

import "fmt"

fmt.Println(ts(1032, 10009))

fmt.Println(ts(44402, 100049))

{{out}}

<pre>

===big.Int===

For the extra credit, we use big.Int from the math/big package of the Go standard library. While the method call syntax is not as easy on the eyes as operator syntax, the package provides modular exponentiation and even the Legendre symbol as the Jacobi function.

 

import (

fmt.Println(&R1)

fmt.Println(&R2)

{{out}}

<pre>

===Library===

It gets better; the library has a ModSqrt function that uses Tonelli-Shanks internally. Output is same as above.

 

import (

fmt.Println(&R1)

fmt.Println(&R2)

=={{header|J}}==

 

Implementation:

 

x (y&|)@^ (y-1)%2

)

end.

y|(,-)r

 

Task examples:

 

7 6

56 tosh 101

791399408049 208600591990

41660815127637347468140745042827704103445750172002x tosh (10^50x)+577

 

=={{header|Java}}==

{{trans|Kotlin}}

{{works with|Java|9}}

import java.util.List;

import java.util.Map;

}

}

{{out}}

<pre>n = 10

root1 = 32102985369940620849741983987300038903725266634508

root2 = 67897014630059379150258016012699961096274733366069</pre>

 

=={{header|Kotlin}}==

{{trans|Go}}

 

import java.math.BigInteger

}

else println("No solution exists")

 

{{out}}

</pre>

 

 

}

 

my $b;

last;

}

}

}

}

 

(44402, 100049),

(665820697, 1000000009),

);

 

{{out}}

<pre>Roots of 10 are (7, 6) mod 13

Roots of 56 are (37, 64) mod 101

Roots of 1030 are (1632, 8377) mod 10009

Roots of 44402 are (30468, 69581) mod 100049

Roots of 665820697 are (378633312, 621366697) mod 1000000009

 

=={{header|PicoLisp}}==

{{trans|Go}}

(de **Mod (X Y N)

(let M 1

(println (ts 665820697 1000000009))

(println (ts 881398088036 1000000000039))

 

{{out}}

(791399408049 208600591990)

(32102985369940620849741983987300038903725266634508 67897014630059379150258016012699961096274733366069)

</pre>

 

{{trans|EchoLisp}}

{{works with|Python|3}}

return pow(a, (p - 1) // 2, p)

 

assert (r * r - n) % p == 0

print("n = %d p = %d" % (n, p))

{{out}}

<pre>

=={{header|Racket}}==

{{trans|EchoLisp}}

 

(require math/number-theory)

(task ttest)

 

 

{{out}}

n = 41660815127637347468140745042827704103445750172002 p = 100000000000000000000000000000000000000000000000577

roots : 32102985369940620849741983987300038903725266634508 67897014630059379150258016012699961096274733366069</pre>

 

=={{header|REXX}}==

{{trans|Python}}

The large numbers cannot reasonably be handled by the pow function shown here.

Numeric Digits 1000000

ttest ='[(10, 13), (56, 101), (1030, 10009), (44402, 100049)]'

If z>'' Then

p=p//z

{{out}}

<pre>n = 10 p = 13

=={{header|Sidef}}==

{{trans|Python}}

legendre(n, p) == 1 || die "not a square (mod p)"

var q = p-1

assert((r*r - n) % p == 0)

say "Roots of #{n} are (#{r}, #{p-r}) mod #{p}"

{{out}}

<pre>

Roots of 881398088036 are (791399408049, 208600591990) mod 1000000000039

Roots of 41660815127637347468140745042827704103445750172002 are (32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069) mod 100000000000000000000000000000000000000000000000577

</pre>

 

=={{header|zkl}}==

{{trans|EchoLisp}}

fcn modEq(a,b,p) { (a-b)%p==0 }

fcn legendre(a,p){ a.powm((p - 1)/2,p) }

}

r

T(665820697,1000000009), T(881398088036,1000000000039),

T("41660815127637347468140745042827704103445750172002", BN(10).pow(50) + 577),

println("n=%d p=%d".fmt(n,p));

println(" roots: %d %d".fmt(r, p-r));

{{out}}

<pre>