Cipolla's algorithm: Difference between revisions
Content added Content deleted
No edit summary |
(Added c#) |
||
Line 75: | Line 75: | ||
* [[Tonelli-Shanks algorithm]] |
* [[Tonelli-Shanks algorithm]] |
||
<br><br> |
<br><br> |
||
=={{header|CS}}== |
|||
<lang csharp>using System; |
|||
using System.Numerics; |
|||
namespace CipollaAlgorithm { |
|||
class Program { |
|||
static readonly BigInteger BIG = BigInteger.Pow(10, 50) + 151; |
|||
private static Tuple<BigInteger, BigInteger, bool> C(string ns, string ps) { |
|||
BigInteger n = BigInteger.Parse(ns); |
|||
BigInteger p = ps.Length > 0 ? BigInteger.Parse(ps) : BIG; |
|||
// Legendre symbol. Returns 1, 0, or p-1 |
|||
BigInteger ls(BigInteger a0) => BigInteger.ModPow(a0, (p - 1) / 2, p); |
|||
// Step 0: validate arguments |
|||
if (ls(n) != 1) { |
|||
return new Tuple<BigInteger, BigInteger, bool>(0, 0, false); |
|||
} |
|||
// Step 1: Find a, omega2 |
|||
BigInteger a = 0; |
|||
BigInteger omega2; |
|||
while (true) { |
|||
omega2 = (a * a + p - n) % p; |
|||
if (ls(omega2) == p - 1) { |
|||
break; |
|||
} |
|||
a += 1; |
|||
} |
|||
// Multiplication in Fp2 |
|||
BigInteger finalOmega = omega2; |
|||
Tuple<BigInteger, BigInteger> mul(Tuple<BigInteger, BigInteger> aa, Tuple<BigInteger, BigInteger> bb) { |
|||
return new Tuple<BigInteger, BigInteger>( |
|||
(aa.Item1 * bb.Item1 + aa.Item2 * bb.Item2 * finalOmega) % p, |
|||
(aa.Item1 * bb.Item2 + bb.Item1 * aa.Item2) % p |
|||
); |
|||
} |
|||
// Step 2: Compute power |
|||
Tuple<BigInteger, BigInteger> r = new Tuple<BigInteger, BigInteger>(1, 0); |
|||
Tuple<BigInteger, BigInteger> s = new Tuple<BigInteger, BigInteger>(a, 1); |
|||
BigInteger nn = ((p + 1) >> 1) % p; |
|||
while (nn > 0) { |
|||
if ((nn & 1) == 1) { |
|||
r = mul(r, s); |
|||
} |
|||
s = mul(s, s); |
|||
nn >>= 1; |
|||
} |
|||
// Step 3: Check x in Fp |
|||
if (r.Item2 != 0) { |
|||
return new Tuple<BigInteger, BigInteger, bool>(0, 0, false); |
|||
} |
|||
// Step 5: Check x * x = n |
|||
if (r.Item1 * r.Item1 % p != n) { |
|||
return new Tuple<BigInteger, BigInteger, bool>(0, 0, false); |
|||
} |
|||
// Step 4: Solutions |
|||
return new Tuple<BigInteger, BigInteger, bool>(r.Item1, p - r.Item1, true); |
|||
} |
|||
static void Main(string[] args) { |
|||
Console.WriteLine(C("10", "13")); |
|||
Console.WriteLine(C("56", "101")); |
|||
Console.WriteLine(C("8218", "10007")); |
|||
Console.WriteLine(C("8219", "10007")); |
|||
Console.WriteLine(C("331575", "1000003")); |
|||
Console.WriteLine(C("665165880", "1000000007")); |
|||
Console.WriteLine(C("881398088036", "1000000000039")); |
|||
Console.WriteLine(C("34035243914635549601583369544560650254325084643201", "")); |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>(6, 7, True) |
|||
(37, 64, True) |
|||
(9872, 135, True) |
|||
(0, 0, False) |
|||
(855842, 144161, True) |
|||
(475131702, 524868305, True) |
|||
(791399408049, 208600591990, True) |
|||
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, True)</pre> |
|||
=={{header|D}}== |
=={{header|D}}== |