AreRelativelyPrime (a,b)
Jsou reálná celá čísla a
a b
nesoudělná? Vrací true
nebo false
.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
BernoulliNumber (n)
Vrátit n
-té Bernoulliho číslo.
Více informací najdete v encyklopediích Wikipedia (text je v angličtině) a Mathworld (text je v angličtině).
ChineseRemainder (a,m)
Alternativní názvy: CRT
Najít pomocí čínské věty o zbytcích x
, které řeší systém zadaný vektorem a
, a zbytky prvků m
.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
CombineFactorizations (a,b)
Jsou-li dány dva rozklady, vrátit rozklad (faktorizaci) součinu.
Viz Factorize.
ConvertFromBase (v,b)
Převést vektor hodnot udávajících mocniny b
na číslo.
ConvertToBase (n,b)
Převést číslo na vektor mocnin prvků o základu b
.
DiscreteLog (n,b,q)
Najít diskrétní logaritmus n
o základu b
v Fq, konečné grupě řádu q
, kde q
je prvočíslo, pomocí Silverova-Pohligova-Hellmanova algoritmu.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
Divides (m,n)
Zkontrolovat dělitelnost (zda m
dělí n
).
EulerPhi (n)
Spočítat Eulerovu funkci fí pro n
, to je počet celých čísel mezi 1 a n
, relativně prvočíselných vůči n
.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
ExactDivision (n,d)
Return n/d
but only if d
divides n
. If d
does not divide n
then this function returns
garbage. This is a lot faster for very large numbers
than the operation n/d
, but it is only
useful if you know that the division is exact.
Factorize (n)
Return factorization of a number as a matrix. The first row is the primes in the factorization (including 1) and the second row are the powers. So for example:
genius>
Factorize(11*11*13)
=
[1 11 13
1 2 1]
Více informací najdete v encyklopedii Wikipedia.
Factors (n)
Return all factors of n
in a vector. This
includes all the non-prime factors as well. It includes 1 and the
number itself. So to print all the perfect numbers
(those that are sums of their factors) up to the number 1000 you
could do (this is clearly very inefficient)
for n=1 to 1000 do (
if MatrixSum (Factors(n)) == 2*n then
print(n)
)
FermatFactorization (n,pokusy)
Zkusit Fermatův rozklad n
na (t-s)*(t+s)
. Pokud to je možné, vrací t
a s
jako vektor, jinak vrací null
. Argument pokusy
určuje počet pokusu, než se výpočet vzdá.
Jedná se o docela dobrý rozklad za předpokladu, že je vaše číslo součinem dvou přibližně stejně velkých čísel.
Více informací najdete v encyklopedii Wikipedia (text je v angličtině).
FindPrimitiveElementMod (q)
Najít první primitivní prvek v Fq, konečné grupě řádu q
. Je samozřejmé, že q
musí být prvočíslo.
FindRandomPrimitiveElementMod (q)
Najít náhodný primitivní prvek v Fq, konečné grupě řádu q
. Je samozřejmé, že q
musí být prvočíslo.
IndexCalculus (n,b,q,S)
Spočítat diskrétní logaritmus n
o základu b
v Fq, konečné grupě řádu q
(q
prvočíslo) pomocí faktorizační báze S
. S
by měl být sloupec prvočísel, pokud možno s druhým sloupcem předpočítaným pomocí IndexCalculusPrecalculation
.
IndexCalculusPrecalculation (b,q,S)
Provést přípravný krok výpočtu funkce IndexCalculus
pro logaritmy o základu b
v Fq, konečné grupě řádu q
(q
prvočíslo), pro faktorizační bázi S
(kde S
je sloupcový vektor prvočísel). Logaritmy budou předpočítány a vráceny v druhém sloupci.
IsEven (n)
Otestovat, zda je celé číslo sudé.
IsMersennePrimeExponent (p)
Zjistit, jestli je kladné celé číslo p
Mersennovo prvočíslo. Tj. zda 2p-1 je prvočíslo. Provádí se to hledáním v tabulce známých hodnot, která je relativně krátká. Viz také MersennePrimeExponents a LucasLehmer.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině), GIMPS (text je v angličtině) a Wikipedia.
IsNthPower (m,n)
Zjistit, jestli je racionální číslo m
perfektní n
-tou mocninou . Viz také IsPerfectPower a IsPerfectSquare.
IsOdd (n)
Otestovat, zda je celé číslo liché.
IsPerfectPower (n)
Zkontrolovat, zda je celé číslo perfekntí mocninou ab.
IsPerfectSquare (n)
Check an integer for being a perfect square of an integer. The number must be an integer. Negative integers are never perfect squares of integers.
IsPrime (n)
Tests primality of integers, for numbers less than 2.5e10 the
answer is deterministic (if Riemann hypothesis is true). For
numbers larger, the probability of a false positive
depends on
IsPrimeMillerRabinReps
. That
is the probability of false positive is 1/4 to the power
IsPrimeMillerRabinReps
. The default
value of 22 yields a probability of about 5.7e-14.
If false
is returned, you can be sure that
the number is a composite. If you want to be absolutely sure
that you have a prime you can use
MillerRabinTestSure
but it may take
a lot longer.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
IsPrimitiveMod (g,q)
Zkontrolovat, zda je g
primitivní v Fq, konečné grupě řádu q
, kde q
je prvočíslo. Pokud q
není prvočíslo, jsou výsledky nesmyslné.
IsPrimitiveModWithPrimeFactors (g,q,f)
Zkontrolovat, zda je g
primitivní v Fq, konečné grupě řádu q
, kde q
je prvočíslo a f
je vektor prvočíselných činitelů q
-1. Pokud q
není prvočíslo, jsou výsledky nesmyslné.
IsPseudoprime (n,b)
Zda je n
pseudoprvočíslo o základu b
, ale ne prvočíslo, tj. jestli b^(n-1) == 1 mod n
. Volá se funkce PseudoprimeTest
.
IsStrongPseudoprime (n,b)
Zjistit, zda je n
silné pseudoprvočíslo o základu b
, ale ne prvočíslo.
Jacobi (a,b)
Alternativní názvy: JacobiSymbol
Spočítat Jacobiho symbol (a/b) (b by mělo být liché).
JacobiKronecker (a,b)
Alternativní názvy: JacobiKroneckerSymbol
Spočítat Jacobiho symbol (a/b) s Kroneckerovým rozšířením (a/2)=(2/a), když a
je liché, nebo (a/2)=0, když a
je sudé.
LeastAbsoluteResidue (a,n)
Vrátit zbytek a
mod n
s nejmenší absolutní hodnotou (v intervalu -n/2 až n/2).
Legendre (a,p)
Alternativní názvy: LegendreSymbol
Spočítat Legendrův symbol (a/p).
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
LucasLehmer (p)
Zjistit pomocí Lucasova-Lehmerova testu, zda je 2p-1 Mersennovo prvočíslo. Viz také MersennePrimeExponents a IsMersennePrimeExponent.
Více informací najdete v encyklopediích Wikipedia (text je v angličtině), Planetmath (text je v angličtině) a Mathworld (text je v agličtině).
LucasNumber (n)
Vrátit n
-té Lucasovo číslo.
Více informací najdete v encyklopediích Wikipedia (text je v angličtině), Planetmath (text je v angličtině) a Mathworld (text je v angličtině).
MaximalPrimePowerFactors (n)
Vrátit všechny maximální mocniny prvočísel v rozkladu čísla.
MersennePrimeExponents
Vektor se známými exponenty Mersennových prvočísel, což je seznam kladných celých čísel p
takových, že 2p-1 je prvočíslo. Viz také IsMersennePrimeExponent a LucasLehmer.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině), GIMPS (text je v angličtině) a Wikipedia.
MillerRabinTest (n,opak)
Use the Miller-Rabin primality test on n
,
reps
number of times. The probability of false
positive is (1/4)^reps
. It is probably
usually better to use
IsPrime
since that is faster and
better on smaller integers.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
MillerRabinTestSure (n)
Použít Millerův-Rabinův test prvočíselnosti na n
s tolika bázemi, že za předpokladu zobecněné Riemannovy hypotézy je výsledek deterministický.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
ModInvert (n,m)
Vrátit převrácenou hodnotu n mod m.
Více informací najdete v encyklopedii Mathworld (text je v angličtině).
MoebiusMu (n)
Vrátit Möbiovu funkci μ vyhodnocenu na n
. Což znamená, že vrátí 0 v případě, že n
není součin různých prvočísel, a (-1)^k
v případě, že je součin k
různých prvočísel.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
NextPrime (n)
Vrátit nejmenší prvočíslo větší než n
. Záporná prvočísla jsou považována za prvočísla, takže předchozí prvočíslo můžete získat jako -NextPrime(-n)
.
Tato funkce používá funkci mpz_nextprime
z knihovny GMP, která zase používá pravděpodobnostní Millerův-Rabinův test (viz také MillerRabinTest
). Pravděpodobnost falešné kladné odpovědi není nastavitelná, ale je dostatečně malá pro praktické účely.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
PadicValuation (n,p)
Vrátit p-adické ohodnocení (počet koncových nul v základu p
).
Více informací najdete v encyklopediích Wikipedia (text je v angličtině) a Planetmath (text je v angličtině).
PowerMod (a,b,m)
Spočítat a^b mod m
. b
-tá mocnina čísla a
modulo m
. Tuto funkci není nutné používat, protože se automaticky použije v režimu modulární aritmetiky. Z tohoto důvodu je a^b mod m
stejně rychlé.
Prime (n)
Alternativní názvy: prime
Vrátit n
-té prvočíslo (až do limitu).
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
PrimeFactors (n)
Vrátit v podobě vektoru všechny prvočinitele čísla.
Více informací najdete v encyklopediích Mathworld (text je v angličtině) a Wikipedia (text je v angličtině).
PseudoprimeTest (n,b)
Pseudoprime test, returns true
if and only if
b^(n-1) == 1 mod n
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
RemoveFactor (n,m)
Odstranit všechny instance činitele m
z čísla n
. Prakticky to znamená, že je poděleno nejvyšší mocninou čísla m
, která je dělitelem n
.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
SilverPohligHellmanWithFactorization (n,b,q,f)
Najít diskrétní logaritmus n
o základu b
v Fq, konečné grupě řádu q
, kde q
je prvočíslo, pomocí Silverova-Pohligova-Hellmanova algoritmu, dané f
je rozkladem q
-1.
SqrtModPrime (n,p)
Najít druhou odmocninu z n
modulo p
(kde p
je prvočíslo). Pokud není kvadratickým zbytkem, je vráceno null.
Více informací najdete v encyklopedicíh Planetmath (text je v angličtině) a Mathworld (text je v angličtině).
StrongPseudoprimeTest (n,b)
Spustit silný test pseudoprvočíselnosti o základu b
na n
.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia (text je v angličtině).
gcd (a,argumenty...)
Alternativní názvy: GCD
Největší společný dělitel celých čísel. V seznamu argumentů můžete uvést libovolný počet celých čísel, nebo je můžete zadat jako vektor nebo matici celých čísel. Pokud zadáte více než jednu matici stejné velikosti, bude největší společný dělitel určen prvek po prvku.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.
lcm (a,argumenty...)
Alternativní názvy: LCM
Nejmenší společný násobek celých čísel. V seznamu argumentů můžete uvést libovolný počet celých čísel, nebo je můžete zadat jako vektor nebo matici celých čísel. Pokud zadáte více než jednu matici stejné velikosti, bude nejmenší společný násobek určen prvek po prvku.
Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.