Cipolla's algorithm: Difference between revisions

Line 75:

* [[Tonelli-Shanks algorithm]]

=={{header|11l}}==

<syntaxhighlight lang=11l>F convertToBase(n, b)

<syntaxhighlight lang="11l">F convertToBase(n, b)

I (n < 2)

R [n]

Line 135:

Line 134:

Roots of 8219 mod 10007: []

</pre>

=={{header|C}}==

<syntaxhighlight lang=c>#include <stdbool.h>

<syntaxhighlight lang="c">#include <stdbool.h>

#include <stdint.h>

#include <stdio.h>

Line 346:

Line 344:

Find solution for n = 665165880 and p = 1000000007

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

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

<syntaxhighlight lang=csharp>using System;

<syntaxhighlight lang="csharp">using System;

using System.Numerics;

Line 434:

Line 431:

(791399408049, 208600591990, True)

(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, True)</pre>

=={{header|D}}==

<syntaxhighlight lang=D>import std.bigint;

<syntaxhighlight lang="d">import std.bigint;

import std.stdio;

import std.typecons;

Line 530:

Line 526:

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)

Line 605:

Line 600:

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

Line 623:

Line 617:

</syntaxhighlight>

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

Line 639:

Line 633:

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

</pre>

=={{header|Factor}}==

<syntaxhighlight lang=factor>USING: accessors assocs interpolate io kernel literals locals

<syntaxhighlight lang="factor">USING: accessors assocs interpolate io kernel literals locals

math math.extras math.functions ;

Line 705:

Line 698:

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.

<syntaxhighlight lang=freebasic>' version 08-04-2017

<syntaxhighlight lang="freebasic">' version 08-04-2017

' compile with: fbc -s console

' maximum for p is 17 digits to be on the save side

Line 920:

Line 912:

===GMP version===

<syntaxhighlight lang=freebasic>' version 12-04-2017

<syntaxhighlight lang="freebasic">' version 12-04-2017

' compile with: fbc -s console

Line 1,092:

Line 1,084:

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.

<syntaxhighlight lang=go>package main

<syntaxhighlight lang="go">package main

import "fmt"

Line 1,169:

Line 1,160:

===big.Int===

Extra credit:

<syntaxhighlight lang=go>package main

<syntaxhighlight lang="go">package main

import (

Line 1,236:

Line 1,227:

17436881171909637738621006042549786426312886309400

</pre>

=={{header|J}}==

Based on the echolisp implementation:

<syntaxhighlight lang=J>leg=: dyad define

<syntaxhighlight lang="j">leg=: dyad define

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

)

Line 1,278:

Line 1,268:

Task examples:

<syntaxhighlight lang=J> 10 cipolla 13

<syntaxhighlight lang="j"> 10 cipolla 13

6 7

56 cipolla 101

Line 1,295:

Line 1,285:

34035243914635549601583369544560650254325084643201x cipolla (10^50x) + 151

17436881171909637738621006042549786426312886309400 82563118828090362261378993957450213573687113690751</syntaxhighlight>

=={{header|Java}}==

<syntaxhighlight lang=~~Java~~>import java.math.BigInteger;

<syntaxhighlight lang="java">import java.math.BigInteger;

import java.util.function.BiFunction;

import java.util.function.Function;

Line 1,416:

Line 1,405:

(791399408049, 208600591990, true)

(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)</pre>

=={{header|jq}}==

Line 1,422:

Line 1,410:

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

<syntaxhighlight lang=jq># To take advantage of gojq's arbitrary-precision integer arithmetic:

<syntaxhighlight lang="jq"># To take advantage of gojq's arbitrary-precision integer arithmetic:

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

Line 1,511:

Line 1,499:

[82563118828090362261378993957450213573687113690751,17436881171909637738621006042549786426312886309400,true]

</pre>

=={{header|Julia}}==

<syntaxhighlight lang=julia>using Primes

<syntaxhighlight lang="julia">using Primes

function legendre(n, p)

Line 1,572:

Line 1,558:

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

</pre>

=={{header|Kotlin}}==

<syntaxhighlight lang=scala>// version 1.2.0

<syntaxhighlight lang="scala">// version 1.2.0

import java.math.BigInteger

Line 1,654:

Line 1,639:

(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)

</pre>

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

<syntaxhighlight lang=~~Mathematica~~>ClearAll[Cipolla]

<syntaxhighlight lang="mathematica">ClearAll[Cipolla]

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

ls = JacobiSymbol[n, p];

Line 1,704:

Line 1,688:

{791399408049,208600591990,True}

{82563118828090362261378993957450213573687113690751,17436881171909637738621006042549786426312886309400,True}</pre>

=={{header|Nim}}==

<syntaxhighlight lang=~~Nim~~>import options

<syntaxhighlight lang="nim">import options

import bignum

Line 1,798:

Line 1,781:

(791399408049, 208600591990)

(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400)</pre>

=={{header|Perl}}==

<syntaxhighlight lang=perl>use bigint;

<syntaxhighlight lang="perl">use bigint;

use ntheory qw(is_prime);

Line 1,861:

Line 1,843:

Roots of 665165880 are (475131702, 524868305) mod 1000000007

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

=={{header|Phix}}==

with javascript_semantics

include mpfr.e

Line 1,974:

Line 1,955:

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

</pre>

=={{header|PicoLisp}}==

<syntaxhighlight lang=~~PicoLisp~~># from @lib/rsa.l

<syntaxhighlight lang="picolisp"># from @lib/rsa.l

(de **Mod (X Y N)

(let M 1

Line 2,049:

Line 2,029:

(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

Line 2,111:

Line 2,090:

Roots of 8219 mod 10007: ()

</pre>

=={{header|Racket}}==

<syntaxhighlight lang=racket>#lang racket

<syntaxhighlight lang="racket">#lang racket

(require math/number-theory)

Line 2,200:

Line 2,178:

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

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

=={{header|Raku}}==

(formerly Perl 6)

Line 2,206:

Line 2,183:

<syntaxhighlight lang=raku line># Legendre operator (𝑛│𝑝)

<syntaxhighlight lang="raku" line># Legendre operator (𝑛│𝑝)

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

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

Line 2,277:

Line 2,254:

Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151

</pre>

=={{header|Sage}}==

def eulerCriterion(a, p):

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

Line 2,349:

Line 2,325:

False

</pre>

=={{header|Scala}}==

===Imperative solution===

<syntaxhighlight lang=~~Scala~~>object CipollasAlgorithm extends App {

<syntaxhighlight lang="scala">object CipollasAlgorithm extends App {

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

Line 2,407:

Line 2,382:

}</syntaxhighlight>

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

<syntaxhighlight lang=ruby>func cipolla(n, p) {

<syntaxhighlight lang="ruby">func cipolla(n, p) {

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

Line 2,468:

Line 2,442:

Roots of 881398088036 are (791399408049 208600591990) mod 1000000000039

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

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

<syntaxhighlight lang=vbnet>Imports System.Numerics

<syntaxhighlight lang="vbnet">Imports System.Numerics

Module Module1

Line 2,552:

Line 2,525:

(791399408049, 208600591990, True)

(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, True)</pre>

=={{header|Wren}}==

<syntaxhighlight lang=ecmascript>import "/big" for BigInt

<syntaxhighlight lang="ecmascript">import "/big" for BigInt

import "/dynamic" for Tuple

Line 2,628:

Line 2,600:

[82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true]

</pre>

=={{header|zkl}}==

Uses lib GMP (GNU MP Bignum Library).

<syntaxhighlight lang=zkl>var [const] BN=Import("zklBigNum"); //libGMP

<syntaxhighlight lang="zkl">var [const] BN=Import("zklBigNum"); //libGMP

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

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

Line 2,663:

Line 2,634:

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

}</syntaxhighlight>

<syntaxhighlight lang=zkl>foreach n,p in (T(

<syntaxhighlight lang="zkl">foreach n,p in (T(

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

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