Integer factorization (original) (raw)
في نظرية الأعداد، التحليل إلى العوامل أو تحليل العدد الصحيح أو التفكيك إلى عوامل أولية، هو عملية تفكيكه إلى جداء عوامله الأولية، أي كتابة هذا العدد غير الأولي على شكل جداء أعداد أولية، بحيث يكون حاصل ضربها مساوٍ للعدد الأصلي. مثلا: تحليل العدد 45 هو 3·3·5 أي 32·5. أمثلة أخرى: 11 = 11 25 = 5 × 5 = 52 125 = 5 × 5 × 5 = 53 360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 32 × 5 1001 = 7 × 11 × 13 1010021 = 17 × 19 × 53 × 59 إذن التفكيك دائما وحيد، وارتباطا مع المبرهنة الأساسية في الحساب. لهذه المعضلة أهمية كبيرة في الرياضيات وفي التشفير وفي نظرية التعقيد وفي الحساب الكمي.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de nombres, la factorització dels enters és el procés de trobar quins nombres primers es multipliquen per fer un nombre compost, doncs els divisors no trivials (diferent de l'1 i del mateix nombre). Aquests nombres primers és diuen «factors». Si es té un algorisme per factoritzar qualsevol enter llavors el mateix algorisme serveix per factoritzar-lo en factors primers a base d'aplicar el mateix algorisme repetidament fins que tots els factors siguin nombres primers. Aquesta factorització es coneix com a descomposició en producte de factors primers o factorització en nombres primers i és el procés de resolució del problema següent: sigui un enter estrictament positiu, com escriure'l en forma d'un producte de nombres primers; per exemple, si el nombre donat és 45, la factorització en nombres primers és 3² × 5. La factorització entera és única, llevat de l'ordre dels factors i la multiplicitat de les unitats positiva i negativa (1 i -1). Per definició, un nombre primer no es pot descompondre. També es pot dir que és el resultat de la seva pròpia descomposició. La factorització és sempre única, d'acord amb el teorema fonamental de l'aritmètica. Ja el 1801, el matemàtic Carl Friedrich Gauss a les seves Disquisicions artimètiques el va assenyalar com un dels grans problemes de l'aritmètica. Té una importància considerable en criptografia, en teoria de la complexitat i per als ordinadors quàntics. Exemples11 = 11 25 = 5 × 5 = 5² 125 = 5 × 5 × 5 = 53 360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 3² × 5 1.001 = 7 × 11 × 13 1.010.021 = 17 × 19 × 53 × 59 (ca) في نظرية الأعداد، التحليل إلى العوامل أو تحليل العدد الصحيح أو التفكيك إلى عوامل أولية، هو عملية تفكيكه إلى جداء عوامله الأولية، أي كتابة هذا العدد غير الأولي على شكل جداء أعداد أولية، بحيث يكون حاصل ضربها مساوٍ للعدد الأصلي. مثلا: تحليل العدد 45 هو 3·3·5 أي 32·5. أمثلة أخرى: 11 = 11 25 = 5 × 5 = 52 125 = 5 × 5 × 5 = 53 360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 32 × 5 1001 = 7 × 11 × 13 1010021 = 17 × 19 × 53 × 59 إذن التفكيك دائما وحيد، وارتباطا مع المبرهنة الأساسية في الحساب. لهذه المعضلة أهمية كبيرة في الرياضيات وفي التشفير وفي نظرية التعقيد وفي الحساب الكمي. (ar) Prvočíselný rozklad je matematický pojem z oboru aritmetiky. Jedná se o vyjádření přirozeného čísla jako součinu mocnin prvočísel. (cs) En nombroteorio, faktorigo de entjero aŭ entjera faktorigo estas la procezo kaj la rezulto de malkomponigo de komponigita nombro en pli malgrandajn nebagatelajn divizoroj, tiel ke multiplikitaj ĉiuj kune la divizoroj estas egalaj la originala entjero. Nebagatela divizoro estas tiu ne egala al 1 kaj ne egala al la fonta entjero. (eo) Die Primfaktorzerlegung ist die Darstellung einer positiven natürlichen Zahl als Produkt aus Primzahlen die dann als Primfaktoren von bezeichnet werden. Diese Darstellung ist eindeutig (bis auf die Reihenfolge der Faktoren; es ist eine Multimenge) und zählt zu den grundlegenden und klassischen Werkzeugen der Zahlentheorie. Sie ist Gegenstand des . Es ist bisher kein effizientes Faktorisierungsverfahren bekannt, um die Primfaktorzerlegung einer beliebigen Zahl zu erhalten. (de) Zenbaki osoen faktorizazioa, zenbakien teorian, zenbaki oso bat zenbaki lehenen biderketa bezala adieraztean datza. Zenbakiak oso handiak badira ez dago arazo hau efizienteki konpondu dezakeen algoritmorik. Adibidez, 232ko digitu zenbaki bat faktorizatzeko, 100 konputagailuko kluster batek 2 urte behar izan zituen, 2009an. Baina digitu kopuruak ez du konplexutasunarekin zerukusirik; faktorizatzeko kasu zailenak, uste denez, bata bestearen gertu dauden bi zenbaki lehenen biderketa bezala faktorizatzen diren zenbakiak dira. Matematikako eta konputagailuen teknologiako arlo asko arazo hau konpontzeko sortu dira, hauen hartean konputazio kuantikoa, eta . (eu) In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are sufficiently large, no efficient non-quantum integer factorization algorithm is known. However, it has not been proven that such an algorithm does not exist. The presumed difficulty of this problem is important for the algorithms used in cryptography such as RSA public-key encryption and the RSA digital signature. Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves, algebraic number theory, and quantum computing. In 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann factored a 240-digit (795-bit) number (RSA-240) utilizing approximately 900 core-years of computing power. The researchers estimated that a 1024-bit RSA modulus would take about 500 times as long. Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are semiprimes, the product of two prime numbers. When they are both large, for instance more than two thousand bits long, randomly chosen, and about the same size (but not too close, for example, to avoid efficient factorization by Fermat's factorization method), even the fastest prime factorization algorithms on the fastest computers can take enough time to make the search impractical; that is, as the number of digits of the primes being factored increases, the number of operations required to perform the factorization on any computer increases drastically. Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem—for example, the RSA problem. An algorithm that efficiently factors an arbitrary integer would render RSA-based public-key cryptography insecure. (en) En mathématiques et plus précisément en arithmétique, la décomposition en produit de facteurs premiers, aussi connue comme la factorisation entière en nombres premiers ou encore plus couramment la décomposition en facteurs premiers, consiste à chercher à écrire un entier naturel non nul sous forme d'un produit de nombres premiers. Par exemple, si le nombre donné est 45, la factorisation en nombres premiers est 32 × 5, soit 3 × 3 × 5. Par définition, un nombre premier ne peut pas être décomposé en produit de plusieurs nombres premiers. On peut aussi dire qu'il est sa propre décomposition. Quant au nombre 1, c'est le produit vide. 5 = 525 = 5 × 5 = 52125 = 5 × 5 × 5 = 53360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 32 × 51 001 = 7 × 11 × 131 010 021 = 17 × 19 × 53 × 59 La factorisation est toujours unique, en accord avec le théorème fondamental de l'arithmétique. L'écriture des nombres entiers en produits de facteurs premiers en facilite la manipulation dans des problèmes de divisibilité, de fraction ou de racine carrée. La recherche d'algorithmes de décomposition est d'une importance considérable en mathématiques, en cryptologie, en théorie de la complexité des algorithmes, et pour les calculateurs quantiques. En 2020, un nombre de 250 chiffres (RSA-250) a été décomposé en facteurs premiers en utilisant environ 2700 cœurs.ans de calcul. (fr) En teoría de números, la factorización de enteros, factorización de primos, factorización en primos o árbol de factorización consiste en descomponer un número compuesto (no primo) en divisores no triviales, que cuando se multiplican dan el número original. Cuando los números son muy grandes no se conoce ningún algoritmo que resuelva eficientemente este problema; un reciente intento de factorizar un número de 200 dígitos tardó 18 meses y consumió más de medio siglo de tiempo de cálculo. Su supuesta dificultad es el núcleo de ciertos algoritmos criptográficos, como el RSA. Muchas áreas de las matemáticas y de las ciencias de la computación, como la teoría algebraica de números, las curvas elípticas o la computación cuántica, están relacionadas con este problema. Descomponer dos números de igual longitud no tiene por qué tener la misma complicación. Actualmente (2006) se considera que los casos más duros son aquellos para los que los factores son dos números primos, elegidos al azar, de aproximadamente el mismo tamaño. (es) Faktorisasi prima adalah pecahan bilangan komposit yang terdiri dari bilangan-bilangan pembagi yang lebih kecil, dan hasil perkalian dari bilangan-bilangan tersebut sama dengan bilangan komposit yang disebutkan. Contohnya, faktorisasi prima bilangan 84 adalah 2x2x3x7, di mana bilangan 2, 3 dan 7 adalah bilangan prima dan bilangan pembagi 84. Sampai sekarang ini masih belum ditemukan algoritme faktorisasi non-kuantum yang efisien. Suatu percobaan faktorisasi bilangan dengan 232 digit yang dilaksanakan pada tahun 2009 oleh beberapa ilmuwan berlangsung selama 2 tahun dengan ratusan komputer. Sifat matematis ini adalah dasarnya algoritme enkripsi berkunci publik RSA. Karena sampai sekarang ini masih belum diketahui teknik untuk mendapatkan hasil faktorisasi prima yang cepat dan efisien, maka enkripsi RSA tergolong sangat aman dan hanya bisa dipecahkan dengan cara paksa (brute force) yang harus memakan waktu bertahun-tahun. Jika pada suatu hari telah ditemukannya algoritme yang mampu memecahkan masalah faktorisasi dalam waktu polinomial, semua enkripsi RSA akan langsung menjadi tidak aman. Dua bilangan berbeda yang memiliki jumlah digit yang sama tidak sama sukar difaktorisasi. Menurut pengetahuan matematis sekarang, bilangan yang paling sulit difaktorisasi adalah bilangan semiprima (yaitu hasil perkalian dua bilangan prima). (in) 소인수분해(영어: prime factorization, integer factorization)는 1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법을 말한다.소인수분해를 일의적으로 결정하는 공식은 아직 발견되지 않았다. 현대 암호 처리에서 소인수분해의 어려움은 중요한 기준이 된다. (ko) In de wiskunde heet het ontbinden in priemfactoren, of alleen het ontbinden in factoren, van een geheel getal n, n>1, het vinden van de delers van n, die priemgetallen zijn. Wanneer zij weer met elkaar worden vermenigvuldigd is de uitkomst weer n. Voor ieder van de gevonden priemgetallen p kan het voorkomen, dat p het getal n meer dan één keer deelt. De hoofdstelling van de rekenkunde zegt dat, afgezien van de volgorde waarin de priemgetallen worden gevonden, die een deler van n zijn, steeds dezelfde priemgetallen worden gevonden. Een priemgetal is per definitie een getal dat niet verder in priemfactoren is te ontbinden. 1 wordt niet meegerekend als priemgetal.Het ontbinden in priemfactoren is een operatie, die alleen wordt uitgevoerd op de gehele getallen groter dan 1. Bijvoorbeeld , 2 tot de 3e macht maal 3 maal 13 tot de 2e macht = 8 x 3 x 169. Het ontbinden van een getal in factoren is onderdeel van de getaltheorie. (nl) 素因数分解 (そいんすうぶんかい、英: prime factorization) とは、ある正の整数を素数の積の形で表すことである。 素因数分解には次のような性質がある。 * 任意の正の整数に対して、素因数分解はただ1通りに決定する（素因数分解の一意性）。 * 素因数分解の結果から、正の約数やその個数、総和などを求めることができる。 例えば48を素因数分解すれば、24×3となる。 インターネットでの認証等で利用されている公開鍵暗号の代表であるRSA暗号の安全性は、巨大な合成数の素因数分解を実用的な時間内に実行することが困難であることと深い関わりがあり、RSA 以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解のアルゴリズムが活発に研究されている。また実際に巨大な合成数の素因数分解の計算機実験も行われている。 通常の素因数分解は、有理整数環 Z で考えるが、一般の代数体の整数環においては、素因数分解の一意性に対応する性質が成り立つとは限らない。 (ja) Primtalsfaktorisering innebär att ett heltal skrivs som en produkt av primtal. Exempelvis har talet 456 faktoriseringen Enligt aritmetikens fundamentalsats har varje positivt heltal en primtalsfaktorisering som är unik om man bortser från faktorernas inbördes ordning. Heltalsfaktorisering kallas den allmännare process i vilken ett heltal skrivs som en produkt av mindre men inte nödvändigtvis prima heltal. Till skillnad från primtalsfaktorisering är resultatet av en heltalsfaktorisering inte alltid unikt. Till exempel är både och giltiga heltalsfaktoriseringar av talet 12. (sv) Факториза́цией натурального числа называется его разложение в произведение простых множителей. Существование и единственность (с точностью до порядка следования множителей) такого разложения следует из основной теоремы арифметики. В отличие от задачи распознавания простоты числа, факторизация предположительно является вычислительно сложной задачей. В настоящее время неизвестно, существует ли эффективный не квантовый алгоритм факторизации целых чисел. Однако доказательства того, что не существует решения этой задачи за полиномиальное время, также нет. Предположение о том, что для больших чисел задача факторизации является вычислительно сложной, лежит в основе широко используемых алгоритмов (например, RSA). Многие области математики и информатики находят применение в решении этой задачи. Среди них: эллиптические кривые, алгебраическая теория чисел и квантовые вычисления. (ru) Na teoria dos números, a fatoração de inteiros é a decomposição de um número composto em um produto de números inteiros menores. Se esses fatores forem ainda mais restritos aos números primos, o processo é denominado fatoração prima. Quando os números são suficientemente grandes, nenhum algoritmo de fatoração de números inteiros não quântico eficiente é conhecido. No entanto, não foi comprovado que não existe um algoritmo eficiente. A suposta dificuldade desse problema está no cerne de algoritmos amplamente usados em criptografia, como o RSA. Muitas áreas da matemática e da ciência da computação foram utilizadas para lidar com o problema, incluindo curvas elípticas, teoria algébrica dos números e computação quântica. Em 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé e Paul Zimmermann fatoraram um número de 240 dígitos (795 bits) (RSA-240) utilizando aproximadamente 900 anos-núcleo de poder de computação. Os pesquisadores estimaram que um módulo RSA de 1024 bits levaria cerca de 500 vezes mais tempo. Nem todos os números de um determinado comprimento são igualmente difíceis de fatorar. Os exemplos mais difíceis desses problemas (para as técnicas atualmente conhecidas) são os semiprimos, o produto de dois números primos. Quando ambos são grandes (mais de dois mil bits de comprimento, por exemplo), escolhidos aleatoriamente e quase do mesmo tamanho (mas não muito próximos para evitar a fatoração eficiente pelo método de fatoração de Fermat, por exemplo), mesmo os algoritmos de fatoração mais rápidos nos computadores mais rápidos podem levar tempo suficiente para tornar a pesquisa impraticável. Isto é, conforme o número de dígitos dos primos sendo fatorados aumenta, o número de operações necessárias para realizar a fatoração em qualquer computador aumenta drasticamente. Muitos protocolos criptográficos são baseados na dificuldade de fatorar grandes inteiros compostos ou um problema relacionado (o problema RSA, por exemplo). Um algoritmo que fatora com eficiência um número inteiro arbitrário tornaria a criptografia de chave pública baseada em RSA insegura. (pt) Факториза́ція цілого числа — розкладання заданого числа на прості множники. На відміну від задачі розпізнавання простоти числа, факторизація ймовірно є складною задачею. (uk) 在數學中，整數分解（英語：integer factorization）又稱質因數分解（prime factorization），是將一個正整數寫成幾個因數的乘積。例如，給出45這個數，它可以分解成。根據算術基本定理，這樣的分解結果應該是獨一無二的。這個問題在代數學、密碼學、計算複雜性理論和量子計算機等領域中有重要意義。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/PrimeDecompositionExample.svg?width=300 |
| dbo:wikiPageExternalLink | http://sourceforge.net/projects/msieve/ https://www.ams.org/bookpages/stml-68 https://www.alpertron.com.ar/ECM.HTM http://mathworld.wolfram.com/news/2005-11-08/rsa-640/ http://citeseer.ist.psu.edu/327036.html http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |
| dbo:wikiPageID | 15491 (xsd:integer) |
| dbo:wikiPageLength | 23476 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1114721791 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quantum_computer dbr:Multiplicative_partition dbr:NP_(complexity) dbr:Primality_test dbr:Algorithm dbc:Integer_factorization_algorithms dbr:Peter_Shor dbr:Cycle_detection dbr:Decision_problem dbr:Canonical_representation_of_a_positive_integer dbr:Elliptic_curve_method dbr:L-notation dbr:Quantum_computing dbr:P-adic_valuation dbr:Cryptography dbr:Mathematics dbr:Generalized_Riemann_hypothesis dbr:Special_number_field_sieve dbr:Prime_factor dbr:RSA_problem dbr:Co-NP dbr:Elliptic_curve dbr:Fundamental_theorem_of_arithmetic dbr:General_number_field_sieve dbr:Generating_set_of_a_group dbr:Greatest_common_divisor dbr:NP-complete dbr:Congruence_of_squares dbr:Continued_fraction_factorization dbr:Shor's_algorithm dbr:Skylake_(microarchitecture) dbc:Computational_hardness_assumptions dbr:Complexity_class dbr:Composite_number dbr:Computational_hardness_assumption dbr:Computer_science dbr:Empty_product dbr:Ideal_class_group dbr:Kronecker_symbol dbr:Pollard's_p_−_1_algorithm dbr:Maurice_Kraitchik dbr:BQP dbr:Adleman–Pomerance–Rumely_primality_test dbr:Time_complexity dbr:Trial_division dbr:Divisor dbr:Hacker's_Delight dbr:AKS_primality_test dbr:Algebraic_number_theory dbc:Unsolved_problems_in_computer_science dbr:Factorization dbr:Number_theory dbr:Partition_(number_theory) dbr:Carl_Pomerance dbr:Digital_Signature_Algorithm dbr:Quadratic_form dbr:Product_(mathematics) dbr:Quadratic_sieve dbr:RSA_numbers dbr:Group_(mathematics) dbr:Bach's_algorithm dbr:Prime_number dbr:Big_O_notation dbr:Bit dbr:Sylow_theorems dbr:Co-NP-complete dbr:Discriminant_of_a_quadratic_form dbr:Donald_Knuth dbr:Aurifeuillean_factorization dbc:Factorization dbr:Manindra_Agrawal dbr:Pollard's_rho_algorithm dbr:Fermat's_factorization_method dbr:Polynomial_time dbr:RSA-240 dbr:RSA_(algorithm) dbr:RSA_(cryptosystem) dbr:RSA_number dbr:Randomized_algorithm dbr:Rational_sieve dbr:Semiprime dbr:Nuclear_magnetic_resonance dbr:Smooth_number dbr:UP_(complexity) dbr:Euler's_factorization_method dbr:Williams'_p_+_1_algorithm dbr:The_Art_of_Computer_Programming dbr:NP-intermediate dbr:Richard_Crandall dbr:Lenstra_elliptic_curve_factorization dbr:Shanks's_square_forms_factorization dbr:Wheel_factorization dbr:Public-key dbr:Dixon's_algorithm dbr:Addison_Wesley dbr:Pearson_Education,_Inc. dbr:Probabilistic_algorithm dbr:Algebraic-group_factorisation_algorithms dbr:File:PrimeDecompositionExample.svg |
| dbp:wikiPageUsesTemplate | dbt:As_of dbt:Authority_control dbt:Cite_book dbt:ISBN dbt:Math dbt:Mvar dbt:Redirect dbt:Reflist dbt:See_also dbt:Short_description dbt:Tmath dbt:Divisor_classes dbt:Number_theoretic_algorithms dbt:Unsolved dbt:Computational_hardness_assumptions |
| dct:subject | dbc:Integer_factorization_algorithms dbc:Computational_hardness_assumptions dbc:Unsolved_problems_in_computer_science dbc:Factorization |
| gold:hypernym | dbr:Decomposition |
| rdf:type | owl:Thing yago:WikicatComputationalHardnessAssumptions yago:WikicatUnsolvedProblemsInComputerScience yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Communication100033020 yago:Condition113920835 yago:DefiniteQuantity113576101 yago:Difficulty114408086 yago:Event100029378 yago:Measure100033615 yago:Message106598915 yago:Number113582013 yago:Postulate106753299 yago:Premise106753800 yago:Prime113594005 yago:PrimeNumber113594302 yago:Problem114410605 yago:Procedure101023820 yago:Proposition106750804 yago:PsychologicalFeature100023100 yago:WikicatIntegerFactorizationAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:State100024720 yago:Statement106722453 yago:WikicatPrimeNumbers |
| rdfs:comment | في نظرية الأعداد، التحليل إلى العوامل أو تحليل العدد الصحيح أو التفكيك إلى عوامل أولية، هو عملية تفكيكه إلى جداء عوامله الأولية، أي كتابة هذا العدد غير الأولي على شكل جداء أعداد أولية، بحيث يكون حاصل ضربها مساوٍ للعدد الأصلي. مثلا: تحليل العدد 45 هو 3·3·5 أي 32·5. أمثلة أخرى: 11 = 11 25 = 5 × 5 = 52 125 = 5 × 5 × 5 = 53 360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 32 × 5 1001 = 7 × 11 × 13 1010021 = 17 × 19 × 53 × 59 إذن التفكيك دائما وحيد، وارتباطا مع المبرهنة الأساسية في الحساب. لهذه المعضلة أهمية كبيرة في الرياضيات وفي التشفير وفي نظرية التعقيد وفي الحساب الكمي. (ar) Prvočíselný rozklad je matematický pojem z oboru aritmetiky. Jedná se o vyjádření přirozeného čísla jako součinu mocnin prvočísel. (cs) En nombroteorio, faktorigo de entjero aŭ entjera faktorigo estas la procezo kaj la rezulto de malkomponigo de komponigita nombro en pli malgrandajn nebagatelajn divizoroj, tiel ke multiplikitaj ĉiuj kune la divizoroj estas egalaj la originala entjero. Nebagatela divizoro estas tiu ne egala al 1 kaj ne egala al la fonta entjero. (eo) Die Primfaktorzerlegung ist die Darstellung einer positiven natürlichen Zahl als Produkt aus Primzahlen die dann als Primfaktoren von bezeichnet werden. Diese Darstellung ist eindeutig (bis auf die Reihenfolge der Faktoren; es ist eine Multimenge) und zählt zu den grundlegenden und klassischen Werkzeugen der Zahlentheorie. Sie ist Gegenstand des . Es ist bisher kein effizientes Faktorisierungsverfahren bekannt, um die Primfaktorzerlegung einer beliebigen Zahl zu erhalten. (de) 소인수분해(영어: prime factorization, integer factorization)는 1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법을 말한다.소인수분해를 일의적으로 결정하는 공식은 아직 발견되지 않았다. 현대 암호 처리에서 소인수분해의 어려움은 중요한 기준이 된다. (ko) 素因数分解 (そいんすうぶんかい、英: prime factorization) とは、ある正の整数を素数の積の形で表すことである。 素因数分解には次のような性質がある。 * 任意の正の整数に対して、素因数分解はただ1通りに決定する（素因数分解の一意性）。 * 素因数分解の結果から、正の約数やその個数、総和などを求めることができる。 例えば48を素因数分解すれば、24×3となる。 インターネットでの認証等で利用されている公開鍵暗号の代表であるRSA暗号の安全性は、巨大な合成数の素因数分解を実用的な時間内に実行することが困難であることと深い関わりがあり、RSA 以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解のアルゴリズムが活発に研究されている。また実際に巨大な合成数の素因数分解の計算機実験も行われている。 通常の素因数分解は、有理整数環 Z で考えるが、一般の代数体の整数環においては、素因数分解の一意性に対応する性質が成り立つとは限らない。 (ja) Primtalsfaktorisering innebär att ett heltal skrivs som en produkt av primtal. Exempelvis har talet 456 faktoriseringen Enligt aritmetikens fundamentalsats har varje positivt heltal en primtalsfaktorisering som är unik om man bortser från faktorernas inbördes ordning. Heltalsfaktorisering kallas den allmännare process i vilken ett heltal skrivs som en produkt av mindre men inte nödvändigtvis prima heltal. Till skillnad från primtalsfaktorisering är resultatet av en heltalsfaktorisering inte alltid unikt. Till exempel är både och giltiga heltalsfaktoriseringar av talet 12. (sv) Факториза́ція цілого числа — розкладання заданого числа на прості множники. На відміну від задачі розпізнавання простоти числа, факторизація ймовірно є складною задачею. (uk) 在數學中，整數分解（英語：integer factorization）又稱質因數分解（prime factorization），是將一個正整數寫成幾個因數的乘積。例如，給出45這個數，它可以分解成。根據算術基本定理，這樣的分解結果應該是獨一無二的。這個問題在代數學、密碼學、計算複雜性理論和量子計算機等領域中有重要意義。 (zh) En teoria de nombres, la factorització dels enters és el procés de trobar quins nombres primers es multipliquen per fer un nombre compost, doncs els divisors no trivials (diferent de l'1 i del mateix nombre). Aquests nombres primers és diuen «factors». Exemples11 = 11 25 = 5 × 5 = 5² 125 = 5 × 5 × 5 = 53 360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 3² × 5 1.001 = 7 × 11 × 13 1.010.021 = 17 × 19 × 53 × 59 (ca) In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. In 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann factored a 240-digit (795-bit) number (RSA-240) utilizing approximately 900 core-years of computing power. The researchers estimated that a 1024-bit RSA modulus would take about 500 times as long. (en) Zenbaki osoen faktorizazioa, zenbakien teorian, zenbaki oso bat zenbaki lehenen biderketa bezala adieraztean datza. Zenbakiak oso handiak badira ez dago arazo hau efizienteki konpondu dezakeen algoritmorik. Adibidez, 232ko digitu zenbaki bat faktorizatzeko, 100 konputagailuko kluster batek 2 urte behar izan zituen, 2009an. Baina digitu kopuruak ez du konplexutasunarekin zerukusirik; faktorizatzeko kasu zailenak, uste denez, bata bestearen gertu dauden bi zenbaki lehenen biderketa bezala faktorizatzen diren zenbakiak dira. (eu) En teoría de números, la factorización de enteros, factorización de primos, factorización en primos o árbol de factorización consiste en descomponer un número compuesto (no primo) en divisores no triviales, que cuando se multiplican dan el número original. Descomponer dos números de igual longitud no tiene por qué tener la misma complicación. Actualmente (2006) se considera que los casos más duros son aquellos para los que los factores son dos números primos, elegidos al azar, de aproximadamente el mismo tamaño. (es) En mathématiques et plus précisément en arithmétique, la décomposition en produit de facteurs premiers, aussi connue comme la factorisation entière en nombres premiers ou encore plus couramment la décomposition en facteurs premiers, consiste à chercher à écrire un entier naturel non nul sous forme d'un produit de nombres premiers. Par exemple, si le nombre donné est 45, la factorisation en nombres premiers est 32 × 5, soit 3 × 3 × 5. 5 = 525 = 5 × 5 = 52125 = 5 × 5 × 5 = 53360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 32 × 51 001 = 7 × 11 × 131 010 021 = 17 × 19 × 53 × 59 (fr) Faktorisasi prima adalah pecahan bilangan komposit yang terdiri dari bilangan-bilangan pembagi yang lebih kecil, dan hasil perkalian dari bilangan-bilangan tersebut sama dengan bilangan komposit yang disebutkan. Contohnya, faktorisasi prima bilangan 84 adalah 2x2x3x7, di mana bilangan 2, 3 dan 7 adalah bilangan prima dan bilangan pembagi 84. Dua bilangan berbeda yang memiliki jumlah digit yang sama tidak sama sukar difaktorisasi. Menurut pengetahuan matematis sekarang, bilangan yang paling sulit difaktorisasi adalah bilangan semiprima (yaitu hasil perkalian dua bilangan prima). (in) In de wiskunde heet het ontbinden in priemfactoren, of alleen het ontbinden in factoren, van een geheel getal n, n>1, het vinden van de delers van n, die priemgetallen zijn. Wanneer zij weer met elkaar worden vermenigvuldigd is de uitkomst weer n. Voor ieder van de gevonden priemgetallen p kan het voorkomen, dat p het getal n meer dan één keer deelt. De hoofdstelling van de rekenkunde zegt dat, afgezien van de volgorde waarin de priemgetallen worden gevonden, die een deler van n zijn, steeds dezelfde priemgetallen worden gevonden. Bijvoorbeeld , (nl) Na teoria dos números, a fatoração de inteiros é a decomposição de um número composto em um produto de números inteiros menores. Se esses fatores forem ainda mais restritos aos números primos, o processo é denominado fatoração prima. Em 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé e Paul Zimmermann fatoraram um número de 240 dígitos (795 bits) (RSA-240) utilizando aproximadamente 900 anos-núcleo de poder de computação. Os pesquisadores estimaram que um módulo RSA de 1024 bits levaria cerca de 500 vezes mais tempo. (pt) Факториза́цией натурального числа называется его разложение в произведение простых множителей. Существование и единственность (с точностью до порядка следования множителей) такого разложения следует из основной теоремы арифметики. В отличие от задачи распознавания простоты числа, факторизация предположительно является вычислительно сложной задачей. В настоящее время неизвестно, существует ли эффективный не квантовый алгоритм факторизации целых чисел. Однако доказательства того, что не существует решения этой задачи за полиномиальное время, также нет. (ru) |
| rdfs:label | تحليل عدد صحيح إلى عوامل (ar) Factorització dels enters (ca) Prvočíselný rozklad (cs) Primfaktorzerlegung (de) Faktorigo de entjero (eo) Zenbaki osoen faktorizazio (eu) Factorización de enteros (es) Décomposition en produit de facteurs premiers (fr) Faktorisasi prima (in) Integer factorization (en) 素因数分解 (ja) 소인수분해 (ko) Ontbinden in priemfactoren (nl) Fatoração de inteiros (pt) Факторизация целых чисел (ru) Primtalsfaktorisering (sv) 整数分解 (zh) Факторизація цілих чисел (uk) |
| rdfs:seeAlso | dbr:Integer_factorization_records |
| owl:sameAs | dbpedia-de:Integer factorization freebase:Integer factorization http://d-nb.info/gnd/4175717-8 yago-res:Integer factorization wikidata:Integer factorization dbpedia-als:Integer factorization dbpedia-ar:Integer factorization dbpedia-ca:Integer factorization dbpedia-cs:Integer factorization dbpedia-da:Integer factorization dbpedia-eo:Integer factorization dbpedia-es:Integer factorization dbpedia-eu:Integer factorization dbpedia-fa:Integer factorization dbpedia-fi:Integer factorization dbpedia-fr:Integer factorization dbpedia-he:Integer factorization dbpedia-hu:Integer factorization dbpedia-id:Integer factorization dbpedia-is:Integer factorization dbpedia-ja:Integer factorization dbpedia-ko:Integer factorization dbpedia-lb:Integer factorization dbpedia-nl:Integer factorization dbpedia-pt:Integer factorization dbpedia-ro:Integer factorization dbpedia-ru:Integer factorization dbpedia-simple:Integer factorization dbpedia-sl:Integer factorization dbpedia-sr:Integer factorization dbpedia-sv:Integer factorization dbpedia-th:Integer factorization dbpedia-tr:Integer factorization dbpedia-uk:Integer factorization dbpedia-vi:Integer factorization dbpedia-zh:Integer factorization https://global.dbpedia.org/id/4VDyY |
| prov:wasDerivedFrom | wikipedia-en:Integer_factorization?oldid=1114721791&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/PrimeDecompositionExample.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Integer_factorization |
| is dbo:knownFor of | dbr:Daniel_Shanks |
| is dbo:wikiPageDisambiguates of | dbr:Factor |
| is dbo:wikiPageRedirects of | dbr:Prime_factorization_algorithm dbr:Factoring_integers dbr:Factor_table dbr:Factor_tree dbr:Factoring_problem dbr:Factoring_tree dbr:Factors_of_an_integer dbr:Integer_factorisation dbr:Algorithms_for_factoring_integers dbr:Integer_Factorization dbr:Prime_Factorization dbr:Prime_decomposition dbr:Prime_factorisation dbr:Prime_factorization dbr:Prime_factorization_algorithms dbr:Integer_factoring dbr:Integer_factorization_algorithms dbr:Integer_factorization_problem dbr:Integer_factors |
| is dbo:wikiPageWikiLink of | dbr:Pretty_Good_Privacy dbr:Primality_certificate dbr:Prime_factorization_algorithm dbr:Pythagorean_prime dbr:Quantum_complexity_theory dbr:Samuel_S._Wagstaff_Jr. dbr:Factor dbr:Factoring_integers dbr:List_of_algorithms dbr:List_of_computability_and_complexity_topics dbr:Multifactorial dbr:Multiplicity_(mathematics) dbr:Primality_test dbr:Algebra_tile dbr:Algebraic-group_factorisation_algorithm dbr:Applications_of_quantum_mechanics dbr:List_of_integer_sequences dbr:List_of_pitch_intervals dbr:Pell's_equation dbr:Peter_Montgomery_(mathematician) dbr:Peter_Shor dbr:Repunit dbr:Cunningham_Project dbr:Cycle_detection dbr:Cyclotomic_polynomial dbr:Incompressibility_method dbr:Index_calculus_algorithm dbr:Index_of_cryptography_articles dbr:Information-based_complexity dbr:Integer_factorization_records dbr:International_Association_for_Cryptologic_Research dbr:Jacobi_symbol dbr:L-notation dbr:Quantum_computing dbr:Leyland_number dbr:List_of_number_theory_topics dbr:Pseudoforest dbr:Timeline_of_quantum_computing_and_communication dbr:Cryptographically_secure_pseudorandom_number_generator dbr:Cryptography dbr:Math_Girls dbr:Mathematics dbr:Maxima_(software) dbr:Elliptic-curve_cryptography dbr:Elliptic_curve_primality dbr:Oblivious_transfer dbr:One-time_pad dbr:One-way_function dbr:Special_number_field_sieve dbr:Quadratic_residue dbr:Quantum_Computing:_A_Gentle_Introduction dbr:Quantum_algorithm dbr:RSA_Award_for_Excellence_in_Mathematics dbr:RSA_problem dbr:Rabin_signature_algorithm dbr:Trailing_zero dbr:Timeline_of_mathematics dbr:Co-NP dbr:Elliptic_curve dbr:Emma_Lehmer dbr:Emmy_Noether dbr:Fundamental_theorem_of_arithmetic dbr:General_number_field_sieve dbr:Glossary_of_quantum_computing dbr:Modular_arithmetic dbr:Möbius_function dbr:Congruence_of_squares dbr:Continued_fraction_factorization dbr:Continuous-variable_quantum_information dbr:Cryptanalysis dbr:Cryptographic_agility dbr:Equidigital_number dbr:Lenore_Blum dbr:Lenstra_elliptic-curve_factorization dbr:Magma_(computer_algebra_system) dbr:Blum–Goldwasser_cryptosystem dbr:Shor's_algorithm dbr:Collision_resistance dbr:Composite_number dbr:Computational_complexity_of_mathematical_operations dbr:Computational_number_theory dbr:Computers_and_Intractability dbr:From_Zero_to_Infinity dbr:Harmonic_divisor_number dbr:Key_size dbr:PPA_(complexity) dbr:PPP_(complexity) dbr:Parity_(mathematics) dbr:Pollard's_p_−_1_algorithm dbr:Public-key_cryptography dbr:Quantum_supremacy dbr:Theoretical_computer_science dbr:Mathematics_in_India_(book) dbr:Medium_of_exchange dbr:BQP dbr:Adele_ring dbr:Time_complexity dbr:Travelling_Salesman_(2012_film) dbr:Trial_division dbr:UBASIC dbr:DarkHotel dbr:William_Stanley_Jevons dbr:Dixon's_factorization_method dbr:GMR_(cryptography) dbr:Gödel_Prize dbr:Kasiski_examination dbr:Lattice-based_cryptography dbr:Security_of_cryptographic_hash_functions dbr:P-complete dbr:TFNP dbr:Texas_Instruments_signing_key_controversy dbr:Twisted_Hessian_curves dbr:Adi_Shamir dbr:Ages_of_Three_Children_puzzle dbr:Cube_(1997_film) dbr:Daniel_J._Bernstein dbr:Daniel_Shanks dbr:Duodecimal dbr:Euclid dbr:Euclidean_algorithm dbr:Euler's_theorem dbr:Euler's_totient_function dbr:Factorization dbr:Fermat_number dbr:André_Gérardin dbr:Parity_of_zero dbr:Partition_(number_theory) dbr:Carl-Gustav_Esseen dbr:Carl_Pomerance dbr:Digit_sum dbr:Discrete_logarithm dbr:Fast_Fourier_transform dbr:Graph_isomorphism dbr:John_Pollard_(mathematician) dbr:Unary_numeral_system dbr:Legendre_symbol dbr:List_of_GNU_Core_Utilities_commands dbr:Zacharias_Dase dbr:Pseudorandom_number_generator dbr:Pollard's_rho_algorithm_for_logarithms dbr:Quadratic_sieve dbr:Quantum_cryptography dbr:RSA_numbers dbr:Rabin_cryptosystem dbr:Ring_learning_with_errors dbr:H._E._Merritt dbr:Japamala dbr:Prime_number dbr:Arjen_Lenstra dbr:APL_syntax_and_symbols dbr:Accumulator_(cryptography) dbr:John_Brillhart dbr:Least_common_multiple dbr:Big_O_notation dbr:Binary_decision_diagram dbr:Block_Lanczos_algorithm dbr:SymPy dbr:TWINKLE dbr:Table_of_Gaussian_integer_factorizations dbr:Co-NP-complete dbr:Code_motion dbr:Coding_theory dbr:Hidden_subgroup_problem dbr:Higher_residuosity_problem dbr:Highly_cototient_number dbr:Highly_totient_number dbr:Home_prime dbr:Tonelli–Shanks_algorithm dbr:Trapdoor_function dbr:Noisy-storage_model dbr:Pre-algebra dbr:Average-case_complexity dbr:BLISS_signature_scheme dbr:Mars_sol dbr:Pollard's_rho_algorithm dbr:Polynomial_ring dbr:Square_(algebra) dbr:Square_root dbr:Classification_of_finite_simple_groups dbr:Fermat's_factorization_method dbr:Fermi–Dirac_prime dbr:Free_abelian_group dbr:Factor_table dbr:Factor_tree dbr:Factoring_problem dbr:Factoring_tree dbr:Factors_of_an_integer dbr:IEEE_P1363 dbr:Integer_factorisation dbr:Algorithms_for_factoring_integers dbr:Michael_O._Rabin dbr:Miller–Rabin_primality_test dbr:RSA_(cryptosystem) dbr:Rational_sieve dbr:Semiprime dbr:Knapsack_cryptosystems dbr:IFC dbr:Mutually_unbiased_bases dbr:Sieve_theory dbr:Smooth_number dbr:TWIRL dbr:UP_(complexity) dbr:Very_smooth_hash dbr:Euler's_factorization_method dbr:Extravagant_number dbr:FRACTRAN dbr:Factorial dbr:Factorization_of_polynomials dbr:List_of_unsolved_problems_in_computer_science dbr:List_of_unsolved_problems_in_mathematics dbr:List_of_volunteer_computing_projects dbr:Paul_Leyland dbr:Finite_group dbr:NP-intermediate dbr:The_Magic_Words_are_Squeamish_Ossifrage dbr:Multiplicative_group_of_integers_modulo_n dbr:Polynomial_evaluation dbr:Integer_Factorization dbr:Safe_and_Sophie_Germain_primes dbr:Time-evolving_block_decimation dbr:Shanks's_square_forms_factorization dbr:Sylvester's_sequence dbr:Table_of_prime_factors dbr:Random_number_generator_attack dbr:Random_oracle dbr:Wheel_factorization dbr:Ring_learning_with_errors_key_exchange dbr:Williams's_p_+_1_algorithm dbr:Prime_Factorization dbr:Prime_decomposition dbr:Prime_factorisation dbr:Prime_factorization dbr:Prime_factorization_algorithms dbr:Integer_factoring dbr:Integer_factorization_algorithms dbr:Integer_factorization_problem dbr:Integer_factors |
| is dbp:knownFor of | dbr:Daniel_Shanks |
| is foaf:primaryTopic of | wikipedia-en:Integer_factorization |
