Package cc.redberry.rings

Class ChineseRemainders

java.lang.Object

cc.redberry.rings.ChineseRemainders

public final class ChineseRemainders
extends Object

Since:

1.0

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	ChineseRemainders.ChineseRemaindersMagic<E>	Magic data to make CRT faster via precomputing Bezout coefficients
static class	ChineseRemainders.ChineseRemaindersMagicZp64

Method Summary

Modifier and Type	Method	Description
static long	ChineseRemainders(long[] primes, long[] remainders)	Runs Chinese Remainders algorithm
static long	ChineseRemainders(long prime1, long prime2, long remainder1, long remainder2)	Runs Chinese Remainders algorithm
static BigInteger	ChineseRemainders(BigInteger[] primes, BigInteger[] remainders)	Runs Chinese Remainders algorithm
static BigInteger	ChineseRemainders(BigInteger prime1, BigInteger prime2, BigInteger remainder1, BigInteger remainder2)	Runs Chinese Remainders algorithm
static long	ChineseRemainders(ChineseRemainders.ChineseRemaindersMagicZp64 magic, long remainder1, long remainder2)	Runs Chinese Remainders algorithm using the precomputed magic (speed's up computation when several invocations with the same magic performed)
static <E> E	ChineseRemainders(Ring<E> ring, ChineseRemainders.ChineseRemaindersMagic<E> magic, E remainder1, E remainder2)	Runs Chinese Remainders algorithm using the precomputed magic (speed's up computation when several invocations with the same magic performed)
static <E> E	ChineseRemainders(Ring<E> ring, E[] primes, E[] remainders)	Runs Chinese Remainders algorithm
static <E> E	ChineseRemainders(Ring<E> ring, E prime1, E prime2, E remainder1, E remainder2)	Runs Chinese Remainders algorithm
static ChineseRemainders.ChineseRemaindersMagicZp64	createMagic(long prime1, long prime2)	Magic for fast repeated Chinese Remainders
static <E> ChineseRemainders.ChineseRemaindersMagic<E>	createMagic(Ring<E> ring, E prime1, E prime2)	Magic for fast repeated Chinese Remainders

Methods inherited from class java.lang.Object

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

Method Detail

ChineseRemainders

public static long ChineseRemainders(long prime1,
                                     long prime2,
                                     long remainder1,
                                     long remainder2)

Runs Chinese Remainders algorithm

Parameters:

prime1 - #1 prime

prime2 - #2 prime

remainder1 - #1 remainder

remainder2 - #2 remainder

Returns:

the result

ChineseRemainders

public static BigInteger ChineseRemainders(BigInteger prime1,
                                           BigInteger prime2,
                                           BigInteger remainder1,
                                           BigInteger remainder2)

Runs Chinese Remainders algorithm

Parameters:

prime1 - #1 prime

prime2 - #2 prime

remainder1 - #1 remainder

remainder2 - #2 remainder

Returns:

the result

ChineseRemainders

public static <E> E ChineseRemainders(Ring<E> ring,
                                      E prime1,
                                      E prime2,
                                      E remainder1,
                                      E remainder2)

Runs Chinese Remainders algorithm

Parameters:

prime1 - #1 prime

prime2 - #2 prime

remainder1 - #1 remainder

remainder2 - #2 remainder

Returns:

the result

ChineseRemainders

public static <E> E ChineseRemainders(Ring<E> ring,
                                      ChineseRemainders.ChineseRemaindersMagic<E> magic,
                                      E remainder1,
                                      E remainder2)

Runs Chinese Remainders algorithm using the precomputed magic (speed's up computation when several invocations with the same magic performed)

Parameters:

ring - the ring

magic - magic (create by createMagic(Ring, Object, Object))

remainder1 - #1 remainder

remainder2 - #2 remainder

Returns:

the result

createMagic

public static <E> ChineseRemainders.ChineseRemaindersMagic<E> createMagic(Ring<E> ring,
                                                                          E prime1,
                                                                          E prime2)

Magic for fast repeated Chinese Remainders

ChineseRemainders

public static long ChineseRemainders(ChineseRemainders.ChineseRemaindersMagicZp64 magic,
                                     long remainder1,
                                     long remainder2)

Runs Chinese Remainders algorithm using the precomputed magic (speed's up computation when several invocations with the same magic performed)

Parameters:

magic - magic structure for fast modular arithmetic (createMagic(long, long)

remainder1 - #1 remainder

remainder2 - #2 remainder

Returns:

the result

createMagic

public static ChineseRemainders.ChineseRemaindersMagicZp64 createMagic(long prime1,
                                                                       long prime2)

Magic for fast repeated Chinese Remainders

ChineseRemainders

public static long ChineseRemainders(long[] primes,
                                     long[] remainders)

Runs Chinese Remainders algorithm

Parameters:

primes - list of coprime numbers

remainders - remainder

Returns:

the result

ChineseRemainders

public static BigInteger ChineseRemainders(BigInteger[] primes,
                                           BigInteger[] remainders)

Runs Chinese Remainders algorithm

Parameters:

primes - list of coprime numbers

remainders - remainder

Returns:

the result

ChineseRemainders

public static <E> E ChineseRemainders(Ring<E> ring,
                                      E[] primes,
                                      E[] remainders)

Runs Chinese Remainders algorithm

Parameters:

ring - the ring

primes - primes

remainders - remainders

Returns:

the result