Θεωρία αριθμών

AreRelativelyPrime
AreRelativelyPrime (a,b)

Είναι οι πραγματικοί ακέραιοι a και b σχετικοί πρώτοι; Επιστρέφει αληθές ή ψευδές.

See Wikipedia or Planetmath or Mathworld for more information.

BernoulliNumber
BernoulliNumber (n)

Επιστρέφει τον nστό αριθμό Bernoulli.

See Wikipedia or Mathworld for more information.

ChineseRemainder
ChineseRemainder (a,m)

Παραλλαγές: CRT

Εύρεση του x που επιλύει το δοσμένο σύστημα με το διάνυσμα a και modulo τα στοιχεία του m, χρησιμοποιώντας το θεώρημα υπολοίπου του Κινέζου.

See Wikipedia or Planetmath or Mathworld for more information.

CombineFactorizations
CombineFactorizations (a,b)

Με δεδομένες δύο παραγοντοποιήσεις, δίνει την παραγοντοποίηση του γινομένου.

Δείτε παραγοντοποίηση.

ConvertFromBase
ConvertFromBase (v,b)

Μετατρέπει ένα διάνυσμα τιμών που δείχνει δυνάμεις του b στον αριθμό a.

ConvertToBase
ConvertToBase (n,b)

Μετατρέπει έναν αριθμό σε ένα διάνυσμα δυνάμεων για στοιχεία στη βάση b.

DiscreteLog
DiscreteLog (n,b,q)

Βρίσκει τον διακριτό λογάριθμο της n με βάση b στην Fq, το πεπερασμένο πεδίο τάξης q, όπου η q είναι ένας πρώτος, χρησιμοποιώντας τον αλγόριθμο Silver-Pohlig-Hellman.

See Wikipedia, Planetmath, or Mathworld for more information.

Divides
Divides (m,n)

Ελέγχει τη διαιρετότητα (αν η m διαιρεί την n).

EulerPhi
EulerPhi (n)

Υπολογίζει τη συνάρτηση φι του Όιλερ για την n, δηλαδή τον αριθμό των ακεραίων μεταξύ 1 και n που είναι σχετικά πρώτοι με την n.

See Wikipedia, Planetmath, or Mathworld for more information.

ExactDivision
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
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]

See Wikipedia for more information.

Factors
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
FermatFactorization (n,tries)

Δοκιμάζει την παραγοντοποίηση Φερμά της n στο (t-s)*(t+s), επιστρέφει τις t και s ως ένα διάνυσμα αν είναι δυνατό, αλλιώς null. Η tries καθορίζει τον αριθμό των προσπαθειών πριν να σταματήσει.

Αυτή είναι μια αρκετά καλή παραγοντοποίηση, αν ο αριθμός σας είναι το γινόμενο δύο παραγόντων που είναι πολύ κοντά μεταξύ τους.

See Wikipedia for more information.

FindPrimitiveElementMod
FindPrimitiveElementMod (q)

Βρίσκει το πρώτο βασικό στοιχείο στην Fq, την πεπερασμένη ομάδα της τάξης q. Φυσικά η q πρέπει να είναι πρώτος.

FindRandomPrimitiveElementMod
FindRandomPrimitiveElementMod (q)

Βρίσκει ένα τυχαίο βασικό στοιχείο στην Fq, την πεπερασμένη ομάδα της τάξης q (το q πρέπει να είναι πρώτος).

IndexCalculus
IndexCalculus (n,b,q,S)

Υπολογίζει τη διακριτή λογαριθμική βάση b του n στο Fq, την πεπερασμένη ομάδα της τάξης q (q είναι ένας πρώτος), χρησιμοποιώντας τη βάση του συντελεστή S. Η S πρέπει να είναι μια στήλη πρώτων πιθανόν με μια δεύτερη στήλη προϋπολογισμένη από την IndexCalculusPrecalculation.

IndexCalculusPrecalculation
IndexCalculusPrecalculation (b,q,S)

Εκτελεί το βήμα προϋπολογισμού του IndexCalculus για λογαρίθμους με βάση b στο Fq, την πεπερασμένη ομάδα της τάξης q (q είναι ένας πρώτος), για τη βάση συντελεστή S (όπου S είναι ένα διάνυσμα στήλης πρώτων). Οι λογάριθμοι θα προϋπολογιστούν και θα επιστραφούν στη δεύτερη στήλη.

IsEven
IsEven (n)

Ελέγχει αν ο ακέραιος είναι άρτιος.

IsMersennePrimeExponent
IsMersennePrimeExponent (p)

Ελέγχει αν ο θετικός ακέραιος p είναι ένας εκθέτης πρώτου Μερσέν. Δηλαδή, αν 2p-1 είναι ένας πρώτος. Το κάνει αναζητώντας τον σε έναν πίνακα γνωστών τιμών που είναι σχετικά σύντομος. Δείτε επίσης MersennePrimeExponents και LucasLehmer.

See Wikipedia, Planetmath, Mathworld or GIMPS for more information.

IsNthPower
IsNthPower (m,n)

Ελέγχει αν ένας ρητός αριθμός m είναι μια τέλεια nστή δύναμη. Δείτε επίσης IsPerfectPower και IsPerfectSquare.

IsOdd
IsOdd (n)

Έλεγχος αν ο ακέραιος είναι περιττός.

IsPerfectPower
IsPerfectPower (n)

Check an integer for being any perfect power, ab.

IsPerfectSquare
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
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.

See Planetmath or Mathworld for more information.

IsPrimitiveMod
IsPrimitiveMod (g,q)

Ελέγχει αν το g είναι βασικό στην Fq, η πεπερασμένη ομάδα της τάξης q, όπου q είναι ένας πρώτος. Αν το q δεν είναι πρώτος τα αποτελέσματα είναι ψευδή.

IsPrimitiveModWithPrimeFactors
IsPrimitiveModWithPrimeFactors (g,q,f)

Ελέγχει αν το g είναι βασικό στην Fq, την πεπερασμένη ομάδα της τάξης q, όπου q είναι ένας πρώτος και το f είναι ένα διάνυσμα πρώτων παραγόντων του q-1. Αν το q δεν είναι πρώτος τα αποτελέσματα είναι ψευδή.

IsPseudoprime
IsPseudoprime (n,b)

Αν το n είναι ένας ψευδοπρώτος με βάση b αλλά όχι ένας πρώτος, δηλαδή αν b^(n-1) == 1 mod n. Αυτό καλεί την PseudoprimeTest

IsStrongPseudoprime
IsStrongPseudoprime (n,b)

Ελέγχει αν το n είναι ένας ισχυρός ψευδοπρώτος με βάση b, αλλά όχι πρώτος.

Jacobi
Jacobi (a,b)

Παραλλαγές: JacobiSymbol

Υπολογίζει το σύμβολο Τζακόμπι (a/b) (το b πρέπει να είναι περιττός).

JacobiKronecker
JacobiKronecker (a,b)

Παραλλαγές: JacobiKroneckerSymbol

Υπολογίζει το σύμβολο Τζακόμπι (a/b) με την επέκταση Κρόνεκερ (a/2)=(2/a) όταν είναι περιττός, ή (a/2)=0 όταν είναι άρτιος.

LeastAbsoluteResidue
LeastAbsoluteResidue (a,n)

Επιστρέφει το υπόλοιπο του a mod n, με την ελάχιστη απόλυτη τιμή (στο διάστημα -n/2 έως n/2).

Legendre
Legendre (a,p)

Παραλλαγές: LegendreSymbol

Υπολογίζει το σύμβολο Λεζάντρ (a/p).

See Planetmath or Mathworld for more information.

LucasLehmer
LucasLehmer (p)

Ελέγχει αν 2p-1 είναι ένας πρώτος Μερσέν χρησιμοποιώντας τη δοκιμή Lucas-Lehmer. Δείτε επίσης MersennePrimeExponents και IsMersennePrimeExponent.

See Wikipedia, Planetmath, or Mathworld for more information.

LucasNumber
LucasNumber (n)

Επιστρέφει τον nστο αριθμό Lucas.

See Wikipedia, Planetmath, or Mathworld for more information.

MaximalPrimePowerFactors
MaximalPrimePowerFactors (n)

Επιστρέφει όλους τους μέγιστους πρώτους παράγοντες δύναμης ενός αριθμού.

MersennePrimeExponents
MersennePrimeExponents

Ένα διάνυσμα με γνωστούς πρώτους εκθέτες Μερσέν, δηλαδή ένας κατάλογος θετικών ακεραίων p έτσι ώστε το 2p-1 να είναι πρώτος. Δείτε επίσης IsMersennePrimeExponent και LucasLehmer.

See Wikipedia, Planetmath, Mathworld or GIMPS for more information.

MillerRabinTest
MillerRabinTest (n,reps)

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.

See Wikipedia or Planetmath or Mathworld for more information.

MillerRabinTestSure
MillerRabinTestSure (n)

Use the Miller-Rabin primality test on n with enough bases that assuming the Generalized Riemann Hypothesis the result is deterministic.

See Wikipedia, Planetmath, or Mathworld for more information.

ModInvert
ModInvert (n,m)

Επιστρέφει τον αντίστροφο του n mod m.

Δείτε Mathworld για περισσότερες πληροφορίες.

MoebiusMu
MoebiusMu (n)

Επιστρέφει την συνάρτηση mu του Moebius υπολογισμένη στο n. Δηλαδή, επιστρέφει 0 αν το n δεν είναι γινόμενο διακριτών πρώτων και (-1)^k αν είναι γινόμενο των k διακριτών πρώτων.

See Planetmath or Mathworld for more information.

NextPrime
NextPrime (n)

Επιστρέφει τον ελάχιστο πρώτο που είναι μεγαλύτερος από τον n. Οι αρνητικοί των πρώτων θεωρούνται πρώτοι και έτσι για να πάρετε τον προηγούμενο πρώτο μπορείτε να χρησιμοποιήσετε -NextPrime(-n).

Αυτή η συνάρτηση χρησιμοποιεί τη mpz_nextprime του GMP που με τη σειρά της χρησιμοποιεί την πιθανοθεωρητική δοκιμή Μίλερ-Ράμπιν (Δείτε επίσης MillerRabinTest). Η πιθανότητα ψευδούς θετικού δεν ρυθμίζεται, αλλά είναι αρκετά χαμηλή για όλους τους πρακτικούς σκοπούς.

See Planetmath or Mathworld for more information.

PadicValuation
PadicValuation (n,p)

Επιστρέφει τον υπολογισμό p-adic (αριθμός των τελικών μηδενικών στη βάση p).

See Wikipedia or Planetmath for more information.

PowerMod
PowerMod (a,b,m)

Compute a^b mod m. The b's power of a modulo m. It is not necessary to use this function as it is automatically used in modulo mode. Hence a^b mod m is just as fast.

Prime
Prime (n)

Παραλλαγές: prime

Επιστρέφει τον nστό πρώτο (μέχρι ένα όριο).

See Planetmath or Mathworld for more information.

PrimeFactors
PrimeFactors (n)

Επιστρέφει όλους τους πρώτους παράγοντες ενός αριθμού ως διάνυσμα.

See Wikipedia or Mathworld for more information.

PseudoprimeTest
PseudoprimeTest (n,b)

Pseudoprime test, returns true if and only if b^(n-1) == 1 mod n

See Planetmath or Mathworld for more information.

RemoveFactor
RemoveFactor (n,m)

Αφαιρεί όλα τα στιγμιότυπα του παράγοντα m από τον αριθμό n. Δηλαδή, διαιρεί με τη μέγιστη δύναμη του m, που διαιρεί το n.

See Planetmath or Mathworld for more information.

SilverPohligHellmanWithFactorization
SilverPohligHellmanWithFactorization (n,b,q,f)

Βρίσκει τους διακριτούς λογάριθμους του n με βάση το b στο Fq, την πεπερασμένη ομάδα της τάξης q, όπου q είναι ένας πρώτος που χρησιμοποιεί τον αλγόριθμο Silver-Pohlig-Hellman, με δεδομένο το f είναι η παραγοντοποίηση του q-1.

SqrtModPrime
SqrtModPrime (n,p)

Βρίσκει την τετραγωνική ρίζα του n modulo p (όπου το p είναι πρώτος). Null επιστρέφεται αν δεν είναι ένα υπόλοιπο δευτεροβάθμιας.

See Planetmath or Mathworld for more information.

StrongPseudoprimeTest
StrongPseudoprimeTest (n,b)

Εκτελεί τη δοκιμή ισχυρού ψευδοπρώτου με βάση b στο n.

See Wikipedia, Planetmath, or Mathworld for more information.

gcd
gcd (a,args...)

Παραλλαγές: GCD

Greatest common divisor of integers. You can enter as many integers as you want in the argument list, or you can give a vector or a matrix of integers. If you give more than one matrix of the same size then GCD is done element by element.

See Wikipedia, Planetmath, or Mathworld for more information.

lcm
lcm (a,args...)

Παραλλαγές: LCM

Least common multiplier of integers. You can enter as many integers as you want in the argument list, or you can give a vector or a matrix of integers. If you give more than one matrix of the same size then LCM is done element by element.

See Wikipedia, Planetmath, or Mathworld for more information.