Cipolla's algorithm: Difference between revisions

* [[Tonelli-Shanks algorithm]]

<br><br>

 

using System.Numerics;

 

}

}

{{out}}

<pre>(6, 7, True)

(791399408049, 208600591990, True)

(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, True)</pre>

=={{header|D}}==

{{trans|Kotlin}}

import std.stdio;

import std.typecons;

writeln(c("881398088036", "1000000000039"));

writeln(c("34035243914635549601583369544560650254325084643201", ""));

{{out}}

<pre>Tuple!(BigInt, "x", BigInt, "y", bool, "b")(6, 7, true)

Tuple!(BigInt, "x", BigInt, "y", bool, "b")(791399408049, 208600591990, true)

Tuple!(BigInt, "x", BigInt, "y", bool, "b")(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)</pre>

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

 

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

=={{header|Java}}==

{{trans|Kotlin}}

{{works with|Java|8}}

import java.util.function.BiFunction;

import java.util.function.Function;

System.out.println(c("34035243914635549601583369544560650254325084643201", ""));

}

{{out}}

<pre>(6, 7, true)

(791399408049, 208600591990, true)

(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)</pre>

 

=={{header|Kotlin}}==

{{trans|Go}}

 

import java.math.BigInteger

println(c("881398088036", "1000000000039"))

println(c("34035243914635549601583369544560650254325084643201", ""))

 

{{out}}

(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)

</pre>

 

=={{header|Perl}}==

use ntheory qw(is_prime);

 

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

: print "No solution for ($n, $p)\n"

{{out}}

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

Roots of 665165880 are (475131702, 524868305) mod 1000000007

Roots of 881398088036 are (791399408049, 208600591990) mod 1000000000039</pre>

{{out}}

</pre>

=={{header|PicoLisp}}==

{{trans|Go}}

(de **Mod (X Y N)

(let M 1

(println (ci 665165880 1000000007))

(println (ci 881398088036 1000000000039))

{{out}}

<pre>

</pre>

=={{header|Python}}==

#Converts n to base b as a list of integers between 0 and b-1

#Most-significant digit on the left

return (x1[0],-x1[0]%p)

 

 

Roots of 8218 mod 10007: (9872, 135)

Roots of 56 mod 101: (37, 64)

{{trans|EchoLisp}}

 

 

(require math/number-theory)

(report-Cipolla 881398088036 1000000000039)

(report-Cipolla 34035243914635549601583369544560650254325084643201

 

{{out}}

Roots of 881398088036 are (208600591990,791399408049) (mod 1000000000039)

Roots of 34035243914635549601583369544560650254325084643201 are (17436881171909637738621006042549786426312886309400,82563118828090362261378993957450213573687113690751) (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|Scala}}==

===Imperative solution===

private val BIG = BigInt(10).pow(50) + BigInt(151)

 

}

 

{{Out}}See it running in your browser by [https://scalafiddle.io/sf/QQBsMza/3 ScalaFiddle (JavaScript, non JVM)] or by [https://scastie.scala-lang.org/NEP5hOWmSBqqpwmF30LpUA Scastie (JVM)].

=={{header|Sidef}}==

{{trans|Go}}

 

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

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

}

{{out}}

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

Roots of 881398088036 are (791399408049 208600591990) mod 1000000000039

Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151</pre>

 

=={{header|zkl}}==

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