Cipolla's algorithm: Difference between revisions

* [[Tonelli-Shanks algorithm]]

<br><br>

 

=={{header|C}}==

{{trans|FreeBasic}}

#include <stdint.h>

#include <stdio.h>

 

return 0;

{{out}}

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

Find solution for n = 665165880 and p = 1000000007

Solution found: x1 = 524868305, x2 = 475131702</pre>

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

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>

 

</pre>

=={{header|F_Sharp|F#}}==

===The function===

This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]

// Cipolla's algorithm. Nigel Galloway: June 16th., 2019

let Cipolla n g =

|_->let n,i=Seq.item α fE in ((Πn*n+Πi*i*b)%g)

if fN 1I n ((g-1I)/2I) g<>1I then None else Some(fL 1I 0I 0 ((g+1I)/2I))

===The Task===

let test=[(10I,13I);(56I,101I);(8218I,10007I);(8219I,10007I);(331575I,1000003I);(665165880I,1000000007I);(881398088036I,1000000000039I);(34035243914635549601583369544560650254325084643201I,10I**50+151I)]

test|>List.iter(fun(n,g)->match Cipolla n g with Some r->printfn "Cipolla %A %A -> %A (%A) check %A" n g r (g-r) ((r*r)%g) |_->printfn "Cipolla %A %A -> has no result" n g)

{{out}}

<pre>

Real: 00:00:00.089, CPU: 00:00:00.090, GC gen0: 2, gen1: 0

</pre>

=={{header|Factor}}==

{{trans|Sidef}}

{{works with|Factor|0.99 2020-08-14}}

math math.extras math.functions ;

 

[ 2dup - [I Roots of ${3} are (${1} ${0}) mod ${2}I] ]

[ [I No solution for (${}, ${})I] ] if* nl

{{out}}

<pre>

Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151

</pre>

=={{header|FreeBASIC}}==

===LongInt version===

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

{{trans|Perl}}

 

function legendre(n, p)

println(r > 0 ? "Roots of $n are ($r, $(p - r)) mod $p." : "No solution for ($n, $p)")

end

<pre>

Roots of 10 are (6, 7) mod 13.

Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151.

</pre>

=={{header|Kotlin}}==

{{trans|Go}}

 

import java.math.BigInteger

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

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

 

{{out}}

(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)

</pre>

=={{header|Nim}}==

{{trans|Kotlin}}

{{libheader|bignum}}

import bignum

 

let sols = c(n, p)

if sols.isSome: echo sols.get()

 

{{out}}

(791399408049, 208600591990)

(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400)</pre>

=={{header|Perl}}==

{{trans|Raku}}

{{libheader|ntheory}}

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>

=={{header|Phix}}==

{{trans|Kotlin}}

{{libheader|Phix/mpfr}}

Obviously were you to use that in anger, you would probably rip out a few mpz_get_str() and return NULL/false rather than "0"/"false", etc.

{{out}}

{"82563118828090362261378993957450213573687113690751","17436881171909637738621006042549786426312886309400","true"}}

</pre>

=={{header|PicoLisp}}==

{{trans|Go}}

(de **Mod (X Y N)

(let M 1

(println (ci 665165880 1000000007))

(println (ci 881398088036 1000000000039))

{{out}}

<pre>

(82563118828090362261378993957450213573687113690751 17436881171909637738621006042549786426312886309400)

</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|Raku}}==

(formerly Perl 6)

{{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|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|Visual Basic .NET}}==

{{trans|C#}}

 

Module Module1

End Sub

 

{{out}}

<pre>(6, 7, True)

(791399408049, 208600591990, True)

(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, True)</pre>

=={{header|Wren}}==

{{trans|Kotlin}}

{{libheader|Wren-big}}

{{libheader|Wren-dynamic}}

 

var Point = Tuple.create("Point", ["x", "y"])

System.print(c.call("665165880", "1000000007"))

System.print(c.call("881398088036", "1000000000039"))

 

{{out}}

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