Tonelli-Shanks algorithm: Difference between revisions
Added pwsh 7 translation from python
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(Added pwsh 7 translation from python) |
||
Line 3,185:
(791399408049 208600591990)
(32102985369940620849741983987300038903725266634508 67897014630059379150258016012699961096274733366069)
</pre>
=={{header|Powershell}}==
{{trans|Python}}
{{works with|Powershell|7}}
<syntaxhighlight lang="powershell">Function Invoke-ModuloExponentiation ([BigInt]$Base, [BigInt]$Exponent, $Modulo) {
$Result = 1
$Base = $Base % $Modulo
If ($Base -eq 0) {return 0}
While ($Exponent -gt 0) {
If (($Exponent -band 1) -eq 1) {$Result = ($Result * $Base) % $Modulo}
$Exponent = $Exponent -shr 1
$Base = ($Base * $Base) % $Modulo
}
return ($Result % $Modulo)
}
Function Get-Legendre ([BigInt]$Integer, [BigInt]$Prime) {
return (Invoke-ModuloExponentiation -Base $Integer -Exponent (($Prime - 1) / 2) -Modulo $Prime)
}
Function Invoke-TonelliShanks ([BigInt]$Integer, [BigInt]$Prime) {
If ((Get-Legendre $Integer $Prime) -ne 1) {throw "$Integer not a square (mod $Prime)"}
[bigint]$q = $Prime - 1
$s = 0
While (($q % 2) -eq 0) {
$q = $q / 2
$s++
}
If ($s -eq 1) {
return (Invoke-ModuloExponentiation $Integer -Exponent (($Prime + 1) / 4) -Modulo $Prime)
}
For ($z = 2; [Bigint]::Compare($z, $Prime) -lt 0; $z++) {
If ([BigInt]::Compare(($Prime - 1), (Get-Legendre $z $Prime)) -eq 0) {
break
}
}
$c = Invoke-ModuloExponentiation -Base $z -Exponent $q -Modulo $Prime
$r = Invoke-ModuloExponentiation -Base $Integer -Exponent (($q + 1) / 2) -Modulo $Prime
$t = Invoke-ModuloExponentiation -Base $Integer -Exponent $q -Modulo $Prime
$m = $s
$t2 = 0
While ((($t - 1) % $Prime) -ne 0) {
$t2 = $t * $t % $Prime
Foreach ($i in (1..$m)) {
If ((($t2 -1) % $Prime) -eq 0) {
break
}
$t2 = Invoke-ModuloExponentiation -Base $t2 -Exponent 2 -Modulo $Prime
}
$b = Invoke-ModuloExponentiation -Base $c -Exponent ([Math]::Pow(2, ($m - $i - 1))) -Modulo $Prime
$r = ($r * $b) % $Prime
$c = ($b * $b) % $Prime
$t = ($t * $c) % $Prime
$m = $i
}
return $r
}
$TonelliTests = @(
@{Integer = [BigInt]::Parse('10'); Prime = [BigInt]::Parse('13')},
@{Integer = [BigInt]::Parse('56'); Prime = [BigInt]::Parse('101')},
@{Integer = [BigInt]::Parse('1030'); Prime = [BigInt]::Parse('10009')},
@{Integer = [BigInt]::Parse('44402'); Prime = [BigInt]::Parse('100049')},
@{Integer = [BigInt]::Parse('665820697'); Prime = [BigInt]::Parse('1000000009')},
@{Integer = [BigInt]::Parse('881398088036'); Prime = [BigInt]::Parse('1000000000039')},
@{Integer = [BigInt]::Parse('41660815127637347468140745042827704103445750172002'); Prime = [BigInt]::Parse('100000000000000000000000000000000000000000000000577')}
)
$TonelliTests | Foreach-Object {
$Result = Invoke-TonelliShanks @TestSplat
[PSCustomObject]@{
n = $TestSplat['Integer']
p = $TestSplat['Prime']
Roots = @($Result, ($TestSplat['Prime'] - $Result))
}
} | Format-List</syntaxhighlight>
{{out}}
<pre>
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
</pre>
| |||