Θεωρία αριθμών
Προηγ | Κεφάλαιο 11. Κατάλογος συναρτήσεων της GEL | Επόμενο

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

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)

  Επιστρέφει `n/d`, αλλά μόνο αν η `d` διαιρεί την `n`. Αν η `d` δεν διαιρεί την `n`, τότε αυτή η συνάρτηση επιστρέφει σκουπίδια. Αυτή είναι πολύ πιο γρήγορη για πολύ μεγάλους αριθμούς από την πράξη `n/d`, αλλά φυσικά χρήσιμη μόνο αν ξέρετε ότι η διαίρεση είναι ακριβής.

Factorize

      Factorize (n)

  Επιστρέφει την παραγοντοποίηση ενός αριθμού ως πίνακα. Η πρώτη γραμμή είναι οι πρώτοι στην παραγοντοποίηση (συμπεριλαμβάνοντας το 1) και η δεύτερη γραμμή είναι οι δυνάμεις. Έτσι για παράδειγμα:

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

  See Wikipedia for more information.

Factors

      Factors (n)

  Επιστρέφει όλους τους παράγοντες της `n` σε ένα διάνυσμα. Αυτή περιλαμβάνει όλους τους μη πρώτους παράγοντες επίσης. Περιλαμβάνει το 1 και τον ίδιο τον αριθμό. Έτσι για παράδειγμα για να εμφανίσετε όλους τους τέλειους αριθμούς (αυτούς που είναι αθροίσματα των παραγόντων τους) μέχρι τον αριθμό 1000 μπορείτε να κάνετε (αυτό φυσικά είναι πολύ ανεπαρκές)

      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 of course never perfect squares of integers.

IsPrime

      IsPrime (n)

  Ελέγχει τους πρώτους αριθμούς ακεραίων, για αριθμούς μικρότερους από 2.5e10 η απάντηση είναι προσδιοριστική (αν η υπόθεση Ρίμαν είναι αληθής). Για αριθμούς μεγαλύτερους, η πιθανότητα ψευδών θετικών εξαρτάται από την `IsPrimeMillerRabinReps`. Δηλαδή, η πιθανότητα ψευδούς θετικού είναι 1/4 στη δύναμη `IsPrimeMillerRabinReps`. Η προεπιλεγμένη τιμή του 22 δίνει μια πιθανότητα περίπου 5.7e-14.

  Αν η `ψευδής` επιστρέφεται, μπορείτε να είστε σίγουροι ότι ο αριθμός είναι σύνθετος. Αν θέλετε να είσαστε ολότελα βέβαιοι ότι έχετε έναν πρώτο μπορείτε να χρησιμοποιήσετε την `MillerRabinTestSure`, αλλά μπορεί να πάρει πολύ περισσότερο.

  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)

  Χρησιμοποιεί τη δοκιμή πρώτων αριθμών Miller-Rabin στο `n`, `reps` είναι ο αριθμός των φορών. Η πιθανότητα ενός ψευδούς θετικού είναι `(1/4)^reps`. Είναι προφανώς συνήθως καλύτερο να χρησιμοποιήσετε `IsPrime` αφού είναι γρηγορότερο και καλύτερο σε μικρότερους ακέραιους.

  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)

  Δοκιμή ψευδοπρώτου, επιστρέφει `αληθές` αν και μόνο αν `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.

Προηγ | Πάνω | Επόμενο
Τριγωνομετρία | Αρχή | Διαχείριση πινάκων