Tonelli-Shanks algorithm: Difference between revisions

{{task}}

 

 

 

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|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}

/* ARM assembly AARCH64 Raspberry PI 3B or android 64 bits */

/* program tonshan64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

{{Output}}

<pre>

Program normal end.

</pre>

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}

/* ARM assembly Raspberry PI or android 32 bits */

/* program tonshan.s */

/***************************************************/

.include "../affichage.inc"

{{Output}}

<pre>

</pre>

=={{header|C}}==

{{trans|C#}}

#include <stdint.h>

#include <stdio.h>

 

return 0;

{{out}}

<pre>n = 10

root1 = 30468

root2 = 69581</pre>

 

=={{header|C sharp|C#}}==

{{trans|Java}}

using System.Collections.Generic;

using System.Numerics;

}

}

{{out}}

<pre>n = 10

root1 = 32102985369940620849741983987300038903725266634508

root2 = 67897014630059379150258016012699961096274733366069</pre>

 

=={{header|Clojure}}==

(defn find-first

" Finds first element of collection that satisifies predicate function pred "

(println (format "n: %5d p: %d \n\troots: %5d %5d" (biginteger n) (biginteger p) (biginteger r) (biginteger (- p r)))))

 

{{out}}

n: 10 p: 13

=={{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>

=={{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|Haskell}}==

{{trans|Python}}

import Data.Bits (shiftR)

 

c' = (b*b) `mod` p

t' = (t*c') `mod` p

 

<pre>λ> tonelli 10 13

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|Julia}}==

 

'''Module''':

 

legendre(a, p) = powermod(a, (p - 1) ÷ 2, p)

end

 

 

'''Main''':

@show TonelliShanks.solve(56, 101)

@show TonelliShanks.solve(1030, 10009)

@show TonelliShanks.solve(665820697, 1000000009)

@show TonelliShanks.solve(881398088036, 1000000000039)

 

{{out}}

=={{header|Kotlin}}==

{{trans|Go}}

 

import java.math.BigInteger

}

else println("No solution exists")

 

{{out}}

Based algorithm pseudo-code, referencing python 3.

 

var t = x mod p

var e = n

run(1032, 10009)

run(44402, 100049)

 

output:

30468 69581

378633312 621366697</pre>

 

=={{header|Perl}}==

{{trans|Raku}}

{{libheader|ntheory}}

use ntheory qw(is_prime powmod kronecker);

 

printf "Roots of %d are (%d, %d) mod %d\n", $n, $t, $p-$t, $p;

}

{{out}}

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

{{trans|C#}}

{{libheader|Phix/mpfr}}

{{out}}

<pre>

=={{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}}

Translation of the Wikipedia pseudocode, heavily influenced by Sidef and Python.

 

sub infix:<│> (Int \𝑛, Int \𝑝 where 𝑝.is-prime && (𝑝 != 2)) {

given 𝑛.expmod( (𝑝-1) div 2, 𝑝 ) {

say "No solution for ({$n}, {$p})." and next if !$t or ($t² - $n) % $p;

say "Roots of $n are ($t, {$p-$t}) mod $p";

 

{{out}}

{{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>

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Module Module1

End Sub

 

{{out}}

<pre>n = 10

{{libheader|Wren-dynamic}}

{{libheader|Wren-big}}

 

var Solution = Tuple.create("Solution", ["root1", "root2", "exists"])

} else {

System.print("No solution exists")

 

{{out}}

=={{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>