About: Fermat's factorization method     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:Event100029378, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FFermat%27s_factorization_method

Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: That difference is algebraically factorable as ; if neither factor equals one, it is a proper factorization of N. Each odd number has such a representation. Indeed, if is a factorization of N, then Since N is odd, then c and d are also odd, so those halves are integers. (A multiple of four is also a difference of squares: let c and d be even.)

AttributesValues
rdf:type
rdfs:label
  • Faktorisierungsmethode von Fermat
  • Fermat's factorization method
  • Método de factorización de Fermat
  • Méthode de factorisation de Fermat
  • Metodo di fattorizzazione di Fermat
  • Fermats factorisatiemethode
  • Algorytm Fermata
  • Método de fatoração de Fermat
  • Метод факторизации Ферма
  • Метод факторизації Ферма
rdfs:comment
  • En arithmétique modulaire, la méthode de factorisation de Fermat est un algorithme de décomposition en produit de facteurs premiers d'un entier naturel.
  • Il metodo di fattorizzazione di Fermat è un algoritmo ideato da Pierre de Fermat per fattorizzare dei numeri interi nei suoi fattori primi. Si basa sulla rappresentazione di un numero come differenza tra due quadrati, ed è più efficace quando esistono due fattori del numero vicini tra loro.
  • Метод факторизации Ферма — алгоритм факторизации (разложения на множители) нечётного целого числа , предложенный Пьером Ферма (1601—1665) в 1643 году. Метод основан на поиске таких целых чисел и , которые удовлетворяют соотношению , что ведёт к разложению .
  • Метод факторизації Ферма — алгоритм факторизації (розклад на множники) непарного цілого числа n, представлений П'єром Ферма (1601—1665) у 1643 році. Метод заснований на пошуку таких цілих чисел і , які задовольняють відношення , що веде до розкладу .
  • Die Faktorisierungsmethode von Fermat ist ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie. Er berechnet zu einer ungeraden, zusammengesetzten Zahl zwei Teiler und , für die gilt. Die Faktorisierungsmethode von Fermat hat nur dann eine gute Laufzeit, wenn sich die zu zerlegende Zahl als Produkt annähernd gleich großer Faktoren darstellen lässt. Sie bildet zudem die Grundlage allgemeiner Faktorisierungsverfahren für große Zahlen, die in der Regel eine bessere Laufzeit aufweisen.
  • Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: That difference is algebraically factorable as ; if neither factor equals one, it is a proper factorization of N. Each odd number has such a representation. Indeed, if is a factorization of N, then Since N is odd, then c and d are also odd, so those halves are integers. (A multiple of four is also a difference of squares: let c and d be even.)
  • El método de factorización de Fermat se basa en la representación de un número natural impar como la : Esa diferencia se puede factorizar algebraicamente como ; si ninguno de esos factores es igual a 1, se trata de una factorización propia de n. Todo número impar se puede representar de esta manera. En efecto, si es una factorización de n, entonces Como n es impar, c y d también son impares, por lo que su semisuma y semidiferencia son ambos enteros. (Un múltiplo de cuatro también es una diferencia de cuadrados: en ese caso se pueden plantear c y d como números pares.)
  • In de getaltheorie is Fermats factorisatiemethode een algoritme voor het ontbinden van een oneven samengesteld getal in twee factoren en , zodat dus . Deze factorisatiemethode is vooral effectief als het getal kan worden voorgesteld als een product ongeveer even grote factoren. De methode vormt ook de basis van algemene factorisatiemethoden voor grote getallen, die minder rekentijd nodig hebben.
  • Algorytm Fermata – metoda faktoryzacji, czyli rozkładu liczby na czynniki pierwsze. Metoda ta szybko znajduje rozkład n jeśli jego dzielniki są bliskie pierwiastkowi kwadratowemu z n. Z powodu istnienia tej metody, tworząc klucze kryptograficzne oparte na iloczynach liczb pierwszych (RSA), unika się iloczynów niewiele różniących się liczb. Działanie algorytmu polega na szukaniu pary liczb a i b takich że
  • O método de fatoração de Fermat, homenageando Pierre de Fermat, baseia-se na representação de um número inteiro ímpar, é representado pela diferença de dois quadrados: A diferença é algebricamente fatorial ; se nenhum fator for igual a um, isso é uma fatoração apropriada para N. Cada número ímpar tem uma unica representação. De fato, se é a fatoração de N, então Desde que N seja ímpar, então c e d também são impares, porque suas metades são inteiras. (Um múltiplo de quatro também é uma diferença de quadrados, desde que c e d também seja.)
foaf:isPrimaryTopicOf
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • Die Faktorisierungsmethode von Fermat ist ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie. Er berechnet zu einer ungeraden, zusammengesetzten Zahl zwei Teiler und , für die gilt. Die Faktorisierungsmethode von Fermat hat nur dann eine gute Laufzeit, wenn sich die zu zerlegende Zahl als Produkt annähernd gleich großer Faktoren darstellen lässt. Sie bildet zudem die Grundlage allgemeiner Faktorisierungsverfahren für große Zahlen, die in der Regel eine bessere Laufzeit aufweisen. Pierre de Fermat beschrieb diese heute nach ihm benannte Faktorisierungsmethode 1643 in einem Brief, der vermutlich an Mersenne oder Frénicle de Bessy adressiert war. In diesem Brief demonstrierte er das Verfahren, indem er die Primfaktorzerlegung von 2.027.651.281 berechnete. Einige Historiker vermuten aber, dass die Methode schon früher bekannt war.
  • Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: That difference is algebraically factorable as ; if neither factor equals one, it is a proper factorization of N. Each odd number has such a representation. Indeed, if is a factorization of N, then Since N is odd, then c and d are also odd, so those halves are integers. (A multiple of four is also a difference of squares: let c and d be even.) In its simplest form, Fermat's method might be even slower than trial division (worst case). Nonetheless, the combination of trial division and Fermat's is more effective than either.
  • El método de factorización de Fermat se basa en la representación de un número natural impar como la : Esa diferencia se puede factorizar algebraicamente como ; si ninguno de esos factores es igual a 1, se trata de una factorización propia de n. Todo número impar se puede representar de esta manera. En efecto, si es una factorización de n, entonces Como n es impar, c y d también son impares, por lo que su semisuma y semidiferencia son ambos enteros. (Un múltiplo de cuatro también es una diferencia de cuadrados: en ese caso se pueden plantear c y d como números pares.) En su forma más simple, el método de Fermat puede ser incluso más lento que el de división por tentativa en el peor de los casos. Sin embargo, la combinación de división por tentativa y el método de Fermat es más efectivo que el uso exclusivo de uno de ellos.
  • En arithmétique modulaire, la méthode de factorisation de Fermat est un algorithme de décomposition en produit de facteurs premiers d'un entier naturel.
  • Il metodo di fattorizzazione di Fermat è un algoritmo ideato da Pierre de Fermat per fattorizzare dei numeri interi nei suoi fattori primi. Si basa sulla rappresentazione di un numero come differenza tra due quadrati, ed è più efficace quando esistono due fattori del numero vicini tra loro.
  • In de getaltheorie is Fermats factorisatiemethode een algoritme voor het ontbinden van een oneven samengesteld getal in twee factoren en , zodat dus . Deze factorisatiemethode is vooral effectief als het getal kan worden voorgesteld als een product ongeveer even grote factoren. De methode vormt ook de basis van algemene factorisatiemethoden voor grote getallen, die minder rekentijd nodig hebben. Pierre de Fermat beschreef in 1643 deze nu naar hem genoemde methode in een brief die vermoedelijk gericht was aan Mersenne of aan . In deze brief liet hij de methode zien door de priemontbinding van het getal 2.027.651.281 te berekenen. Sommige historici vermoeden echter dat de methode reeds eerder bekend was.
  • O método de fatoração de Fermat, homenageando Pierre de Fermat, baseia-se na representação de um número inteiro ímpar, é representado pela diferença de dois quadrados: A diferença é algebricamente fatorial ; se nenhum fator for igual a um, isso é uma fatoração apropriada para N. Cada número ímpar tem uma unica representação. De fato, se é a fatoração de N, então Desde que N seja ímpar, então c e d também são impares, porque suas metades são inteiras. (Um múltiplo de quatro também é uma diferença de quadrados, desde que c e d também seja.) Em sua forma mais simples, o método de Fermat pode ser ainda mais lento do que a divisão comum (no pior caso). No entanto, a combinação de divisão comum e do método de Fermat é mais eficaz do que qualquer outro.
  • Algorytm Fermata – metoda faktoryzacji, czyli rozkładu liczby na czynniki pierwsze. Metoda ta szybko znajduje rozkład n jeśli jego dzielniki są bliskie pierwiastkowi kwadratowemu z n. Z powodu istnienia tej metody, tworząc klucze kryptograficzne oparte na iloczynach liczb pierwszych (RSA), unika się iloczynów niewiele różniących się liczb. Działanie algorytmu polega na szukaniu pary liczb a i b takich że Tę różnicę można przedstawić jako iloczyn (a + b)(a − b); Jeśli żaden z tych czynników nie jest równy jeden, otrzymujemy faktoryzację n. Warto zauważyć, że dla każdego nieparzystego n istnieje taka para liczb. Jeśli n=cd, to W najgorszym przypadku algorytm Fermata może działać wolniej niż naiwne szukanie dzielników n, dlatego nie ma on praktycznego zastosowania. Jego zasada działania stanowi jednak podstawę znacznie efektywniejszych algorytmów faktoryzacji, takich jak sito kwadratowe i GNFS.
  • Метод факторизации Ферма — алгоритм факторизации (разложения на множители) нечётного целого числа , предложенный Пьером Ферма (1601—1665) в 1643 году. Метод основан на поиске таких целых чисел и , которые удовлетворяют соотношению , что ведёт к разложению .
  • Метод факторизації Ферма — алгоритм факторизації (розклад на множники) непарного цілого числа n, представлений П'єром Ферма (1601—1665) у 1643 році. Метод заснований на пошуку таких цілих чисел і , які задовольняють відношення , що веде до розкладу .
prov:wasDerivedFrom
page length (characters) of wiki page
is foaf:primaryTopic of
is Link from a Wikipage to another Wikipage of
Faceted Search & Find service v1.17_git51 as of Sep 16 2020


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3319 as of Dec 29 2020, on Linux (x86_64-centos_6-linux-glibc2.12), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2021 OpenLink Software