Cipolla's algorithm: Difference between revisions

{{trans|Python}}

I (n < 2)

R [n]

print(‘Roots of 56 mod 101: ’cipolla(56, 101))

print(‘Roots of 1 mod 11: ’cipolla(1, 11))

{{out}}

=={{header|C}}==

{{trans|FreeBasic}}

#include <stdint.h>

#include <stdio.h>

return 0;

{{out}}

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

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

using System.Numerics;

}

}

{{out}}

<pre>(6, 7, True)

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

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

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

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

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

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

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)

A Point is represented by a numeric array of length two (i.e. [x,y]).

def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);

;

{{out}}

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

=={{header|Kotlin}}==

{{trans|Go}}

import java.math.BigInteger

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

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

{{out}}

=={{header|Mathematica}}/{{header|Wolfram Language}}==

Cipolla[n_, p_] := Module[{ls, omega2, nn, a, r, s},

ls = JacobiSymbol[n, p];

Cipolla[665165880, 1000000007]

Cipolla[881398088036, 1000000000039]

{{out}}

<pre>{6,7,True}

{{trans|Kotlin}}

{{libheader|bignum}}

import bignum

let sols = c(n, p)

if sols.isSome: echo sols.get()

{{out}}

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

{{trans|Kotlin}}

{{libheader|Phix/mpfr}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>

<span style="color: #0000FF;">?{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cipolla</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)}</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

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

=={{header|PicoLisp}}==

{{trans|Go}}

(de **Mod (X Y N)

(let M 1

(println (ci 665165880 1000000007))

(println (ci 881398088036 1000000000039))

{{out}}

<pre>

=={{header|Python}}==

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

#Most-significant digit on the left

print "Roots of 1 mod 11: " +str(cipolla(1,11))

print "Roots of 8219 mod 10007: " +str(cipolla(8219,10007))

{{out}}

{{trans|EchoLisp}}

(require math/number-theory)

(report-Cipolla 881398088036 1000000000039)

(report-Cipolla 34035243914635549601583369544560650254325084643201

{{out}}

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

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

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

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

{{trans|C#}}

Module Module1

End Sub

{{out}}

<pre>(6, 7, True)

{{libheader|Wren-big}}

{{libheader|Wren-dynamic}}

import "/dynamic" for Tuple

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>