74 lines
1.5 KiB
C#
74 lines
1.5 KiB
C#
using System;
|
|
using sharp.extensions;
|
|
|
|
namespace BigInt
|
|
{
|
|
public static class Euclid
|
|
{
|
|
|
|
public static Tripple<Integer> extended(Integer a, Integer b)
|
|
{
|
|
if (b.isZero()){
|
|
if (a != Integer.ONE){
|
|
throw new ArgumentException("Euclid found GCD>1!");
|
|
}
|
|
return new Tripple<Integer>(a, Integer.ONE, Integer.ZERO);
|
|
}
|
|
Tripple<Integer> r = extended(b, a % b);
|
|
return new Tripple<Integer>(r.X,r.Z,r.Y - ((a / b) * r.Z) );
|
|
}
|
|
|
|
/**
|
|
* Implementation of inverse() like found at
|
|
* https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm (14 Oct 2017)
|
|
**/
|
|
public static Integer inverse(Integer a,Integer m){
|
|
Integer one, zero;
|
|
|
|
rt act, next, future;
|
|
|
|
one = Integer.ONE;
|
|
zero = Integer.ZERO;
|
|
|
|
act = new rt(m, zero);
|
|
next = new rt(a, one);
|
|
|
|
while (!next.r.isZero())
|
|
{
|
|
Integer q = act.r / next.r;
|
|
future = new rt(
|
|
act.r - (q * next.r),
|
|
act.t - (q * next.t)
|
|
);
|
|
|
|
//Console.WriteLine("EUCLID: q = {0}",q);
|
|
//Console.WriteLine("EUCLID: act: r = {0} / t = {1}",act.r,act.t);
|
|
//Console.WriteLine("EUCLID: next: r = {0} / t = {1}",next.r,next.t);
|
|
//Console.WriteLine("EUCLID: future: r = {0} / t = {1}",future.r,future.t);
|
|
|
|
act = next;
|
|
next = future;
|
|
}
|
|
|
|
if (act.r > one){
|
|
return null;
|
|
}
|
|
if (act.t < 0){
|
|
act.t += m;
|
|
}
|
|
|
|
return act.t;
|
|
}
|
|
|
|
private struct rt {
|
|
public Integer r, t;
|
|
|
|
public rt(Integer r,Integer t){
|
|
this.r = r;
|
|
this.t = t;
|
|
}
|
|
}
|
|
|
|
}
|
|
}
|