Cipolla's algorithm: Difference between revisions

* [[Tonelli-Shanks algorithm]]

<br><br>

 

=={{header|EchoLisp}}==

(lib 'struct)

(lib 'types)

(assert (mod= n (* x x) p)) ;; checking the result

(printf "Roots of %d are (%d,%d) (mod %d)" n x (% (- p x) p) p))

{{out}}

<pre>

(% ( * 855842 855842) 1000003) → 331575

 

</pre>

=={{header|FreeBASIC}}==

Had a close look at the EchoLisp code for step 2.

Used the FreeBASIC code from the Miller-Rabin task for prime testing.

' 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

 

 

Type fp2

End Type

 

Data "34035243914635549601583369544560650254325084643201" ', 10^50 + 151

 

 

Dim As fp2 r

 

 

Return r

End Function

 

 

Return fp2mul(a, a, p, w2)

End Function

 

 

Return a

End If

Return fp2square(fp2pow(a, n, p, w2), p, w2)

Else

Return fp2mul(a, fp2pow(a, n, p, w2), p, w2)

End If

' ------=< MAIN >=------

 

Dim As ZString Ptr zstr

Dim As String n_str, p_str

 

 

Dim As fp2 answer

 

For i = 1 To 8

Read n_str

If i < 8 Then

Read p_str

Else

p_str = "10^50 + 151" ' set up last n

End If

 

 

Print p_str; "is not a odd prime"

Print

 

' p is checked and is a odd prime

Print n_str; " is not a square in F"; p_str

Print

End If

 

Do

Do

Do

 

 

answer = fp2pow(answer, p2, p, w2)

 

Loop

 

Next

 

 

' empty keyboard buffer

Print : Print "hit any key to end program"

Sleep

{{out}}

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

Find solution for n = 34035243914635549601583369544560650254325084643201 and p = 10^50 + 151

Solution found: x1 = 17436881171909637738621006042549786426312886309400, x2 = 82563118828090362261378993957450213573687113690751</pre>

=={{header|Go}}==

===int===

Implementation following the pseudocode in the task description.

 

import "fmt"

fmt.Println(c(8219, 10007))

fmt.Println(c(331575, 1000003))

{{out}}

<pre>

===big.Int===

Extra credit:

 

import (

fmt.Println(&R1)

fmt.Println(&R2)

{{out}}

<pre>

17436881171909637738621006042549786426312886309400

</pre>

=={{header|J}}==

 

Based on the echolisp implementation:

 

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

)

assert. 'not a valid square root'

end.

 

Task examples:

 

6 7

56 cipolla 101

208600591990 791399408049

34035243914635549601583369544560650254325084643201x cipolla (10^50x) + 151

 

{{works with|Rakudo|2016.10}}

{{trans|Sidef}}

 

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

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

!! "No solution for ($n, $p)"

}

{{out}}

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

Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151

</pre>

=={{header|Sage}}==

{{works with|Sage|7.6}}

def eulerCriterion(a, p):

return -1 if pow(a, int((p-1)/2), p) == p-1 else 1

 

return sorted(out)

{{out}}

<pre>

False

</pre>

 

=={{header|Sidef}}==

{{trans|Go}}

 

legendre(n, p) == 1 || return nil

say "No solution for (#{n}, #{p})"

}

{{out}}

Roots of 56 are (37 64) mod 101

Roots of 8218 are (9872 135) mod 10007

Roots of 665165880 are (475131702 524868305) mod 1000000007

Roots of 881398088036 are (791399408049 208600591990) mod 1000000000039

</pre>

 

{{trans|EchoLisp}}

Uses lib GMP (GNU MP Bignum Library).

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

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

println("Roots of %d are (%d,%d) (mod %d)".fmt(n,x,(p-x)%p,p));

return(x,(p-x)%p);

T(10,13),T(56,101),T(8218,10007),T(8219,10007),T(331575,1000003),

T(665165880,1000000007),T(881398088036,1000000000039),

BN(10).pow(50) + 151) )){

try{ Cipolla(n,p) }catch{ println(__exception) }

{{out}}

<pre>