75 lines
2.7 KiB
Plaintext
75 lines
2.7 KiB
Plaintext
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 @_
|
|
[PSCustomObject]@{
|
|
n = $_['Integer']
|
|
p = $_['Prime']
|
|
Roots = @($Result, ($_['Prime'] - $Result))
|
|
}
|
|
} | Format-List
|