Teorie čísel

AreRelativelyPrime
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
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
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
CombineFactorizations (a,b)

Jsou-li dány dva rozklady, vrátit rozklad (faktorizaci) součinu.

Viz Factorize.

ConvertFromBase
ConvertFromBase (v,b)

Převést vektor hodnot udávajících mocniny b na číslo.

ConvertToBase
ConvertToBase (n,b)

Převést číslo na vektor mocnin prvků o základu b.

DiscreteLog
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
Divides (m,n)

Zkontrolovat dělitelnost (zda m dělí n).

EulerPhi
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
ExactDivision (n,d)

Vrátit n/d, ale jen pokud d dělí n. Pokud d nedělí n, vrací funkce nesmysly. Pro velmi velká čísla je to rychlejší než operace n/d, ale je to samozřejmě použitelné jen v případě, kdy přesně víte, co dělíte.

Factorize
Factorize (n)

Vrátit rozklad (faktorizaci) čísla jako matici. První řádek jsou prvočísla v rozkladu (včetně 1) a druhý řádek jsou mocnitelé. Takže například

genius> Factorize(11*11*13)
=
[1      11      13
 1      2       1]

Více informací najdete v encyklopedii Wikipedia.

Factors
Factors (n)

Vrátit všechny činitele čísla n jako vektor. Součástí jsou i neprvočíselní činitelé, což zahrnuje také 1 a přímo ono číslo. Takže například pro výpis všech dokonalých čísel (to jsou taková, která jsou součtem všech svých činitelů) až do 1000 můžete udělat toto (je to však značně neefektivní)

for n=1 to 1000 do (
    if MatrixSum (Factors(n)) == 2*n then
        print(n)
)
FermatFactorization
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
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
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
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
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
IsEven (n)

Otestovat, zda je celé číslo sudé.

IsMersennePrimeExponent
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
IsNthPower (m,n)

Zjistit, jestli je racionální číslo m perfektní n-tou mocninou . Viz také IsPerfectPower a IsPerfectSquare.

IsOdd
IsOdd (n)

Otestovat, zda je celé číslo liché.

IsPerfectPower
IsPerfectPower (n)

Zkontrolovat, zda je celé číslo perfekntí mocninou ab.

IsPerfectSquare
IsPerfectSquare (n)

Zkontrolovat, zda je celé číslo perfektní druhou mocninou celého čísla. Číslo musí být celé číslo. Záporná celá čísla samozřejmě perfektními druhými mocninami celých čísel být nemohou.

IsPrime
IsPrime (n)

Testuje prvočíselnost celých čísel, pro čísla menší než 2.5e10 je odpověď deterministická (tedy pokud je Riemannova hypotéza platná). Pro větší čísla závisí falešné kladné odpovědi na IsPrimeMillerRabinReps. Což znamená, že pravděpodobnost nesprávné kladné odpovědi je ¼ umocněná na IsPrimeMillerRabinReps. Výchozí hodnota 22 dává pravděpodobnost zhruba 5.7e-14.

Když je vráceno false, můžete si být jisti, že se jedná o složené číslo. Jestliže si potřebujete být absolutně jistí, že máte prvočíslo, můžete použít funkci MillerRabinTestSure, ale může to trvat trochu déle.

Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.

IsPrimitiveMod
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
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
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
IsStrongPseudoprime (n,b)

Zjistit, zda je n silné pseudoprvočíslo o základu b, ale ne prvočíslo.

Jacobi
Jacobi (a,b)

Alternativní názvy: JacobiSymbol

Spočítat Jacobiho symbol (a/b) (b by mělo být liché).

JacobiKronecker
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
LeastAbsoluteResidue (a,n)

Vrátit zbytek a mod n s nejmenší absolutní hodnotou (v intervalu -n/2 až n/2).

Legendre
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
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
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
MaximalPrimePowerFactors (n)

Vrátit všechny maximální mocniny prvočísel v rozkladu čísla.

MersennePrimeExponents
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
MillerRabinTest (n,opak)

Použít Millerův-Rabinův test prvočíselnosti na n, opak udává kolikrát. Pravděpodobnost falešné kladné odpovědi je (1/4)^opak. Pravděpodobně je obvykle lepší použít funkci IsPrime, protože je rychlejší a lepší u menších celých čísel.

Více informací najdete v encyklopediích Planetmath (text je v angličtině), Mathworld (text je v angličtině) a Wikipedia.

MillerRabinTestSure
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
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
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
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
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
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
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
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
PseudoprimeTest (n,b)

Test pseudoprvočíselnosti, vrací true když a jen když 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
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
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
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
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
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
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.