cc.redberry.rings

Class RationalReconstruction

java.lang.Object

cc.redberry.rings.RationalReconstruction

public final class RationalReconstruction
extends Object

Since:

2.3

Method Summary

Modifier and Type	Method and Description
static BigInteger[]	reconstruct(BigInteger n, BigInteger modulus, BigInteger numeratorBound, BigInteger denominatorBound) Performs a rational number reconstruction.
static long[]	reconstruct(long n, long modulus, long numeratorBound, long denominatorBound) Performs a rational number reconstruction.
static <Poly extends IUnivariatePolynomial<Poly>> Poly[]	reconstruct(Poly n, Poly modulus, int numeratorBound, int denominatorBound) Performs a rational number reconstruction.
static BigInteger[]	reconstructFarey(BigInteger n, BigInteger modulus) Performs a rational number reconstruction via Farey images, that is reconstructuction with bound B = sqrt(N/2 - 1/2)
static BigInteger[]	reconstructFareyErrorTolerant(BigInteger n, BigInteger modulus) Performs a error tolerant rational number reconstruction as described in Algorithm 5 of Janko Boehm, Wolfram Decker, Claus Fieker, Gerhard Pfister, "The use of Bad Primes in Rational Reconstruction", https://arxiv.org/abs/1207.1651v2

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

reconstruct

public static long[] reconstruct(long n,
                                 long modulus,
                                 long numeratorBound,
                                 long denominatorBound)

Performs a rational number reconstruction. If the answer is not unique, null is returned.

Parameters:

n - num * den^(-1) mod modulus

modulus - the modulus

numeratorBound - numerator bound

denominatorBound - denominator bound

reconstruct

public static BigInteger[] reconstruct(BigInteger n,
                                       BigInteger modulus,
                                       BigInteger numeratorBound,
                                       BigInteger denominatorBound)

Performs a rational number reconstruction. If the answer is not unique, null is returned.

reconstructFarey

public static BigInteger[] reconstructFarey(BigInteger n,
                                            BigInteger modulus)

Performs a rational number reconstruction via Farey images, that is reconstructuction with bound B = sqrt(N/2 - 1/2)

reconstructFareyErrorTolerant

public static BigInteger[] reconstructFareyErrorTolerant(BigInteger n,
                                                         BigInteger modulus)

Performs a error tolerant rational number reconstruction as described in Algorithm 5 of Janko Boehm, Wolfram Decker, Claus Fieker, Gerhard Pfister, "The use of Bad Primes in Rational Reconstruction", https://arxiv.org/abs/1207.1651v2

reconstruct

public static <Poly extends IUnivariatePolynomial<Poly>> Poly[] reconstruct(Poly n,
                                                                            Poly modulus,
                                                                            int numeratorBound,
                                                                            int denominatorBound)

Performs a rational number reconstruction. If the answer is not unique, null is returned.

Parameters:

n - num * den^(-1) mod modulus

modulus - the modulus

numeratorBound - numerator bound

denominatorBound - denominator bound