Het in rekening brengen van zeer grote getallen in hun priemgetallen "bouwstenen" is buitengewoon moeilijk voor klassieke computers, en deze moeilijkheid ligt ten grondslag aan de veiligheid van veel cryptografische algoritmen. Hoewel het gemakkelijk is om het getal 20 te ontbinden als het product van de priemgetallen 2 x 2 x 5, bijvoorbeeld, het ontbinden van grotere getallen wordt exponentieel moeilijker bij het gebruik van klassieke factoringalgoritmen.

In een nieuw artikel gepubliceerd in Fysieke beoordeling A , natuurkundigen Jose Luis Rosales en Vicente Martin hebben een methode ontwikkeld die het veel gemakkelijker kan maken om zeer grote getallen te ontbinden waarvan bekend is dat ze precies twee priemfactoren hebben. De nieuwe methode bepaalt de kans dat een priemgetal een van de twee priemfactoren van een bepaald getal is. Na het bepalen van deze kansen, de meest waarschijnlijke primefactorkandidaten kunnen als eerste worden getest, waardoor de priemfactoren veel sneller dan voorheen kunnen worden geïdentificeerd.

"De theorie laat niet alleen zien waar de priemgetallen zich bevinden, maar ook de kans dat een priemgetal een factor is van een gegeven getal, " vertelde Rosales Phys.org . "Natuurlijk, dit heeft implicaties in cryptografie omdat [het cryptosysteem] RSA deze regelmaat negeert."

Een van de interessante dingen van de nieuwe methode is dat er geen computer wordt gebruikt, klassiek of kwantum. In plaats daarvan gaat het om een ​​fysiek kwantumsysteem - een 'kwantumsimulator' - dat, wanneer gecodeerd met het te ontbinden getal, vertoont een kansverdeling van energiewaarden die gelijk is aan de kansverdeling van de priemfactorkandidaten van het gecodeerde getal.

"Ons doel is om een ​​nieuwe kwantumtheorie van het factorisatieprobleem te ontwikkelen met behulp van een kwantumsimulator, " zei Rosales. "Onze aanpak heeft een eigenschap ontdekt zonder klassieke analogie in de getaltheorie. Elk paar priemgetallen dat het probleem oplost, herschikt zichzelf om een ​​regelmatig patroon te vormen:het bandenspectrum van de kwantumsimulator."

Het algemene idee achter de kwantumsimulator is iets dat het "factorisatie-ensemble, " die de onderzoekers eerder introduceerden. Het is gebaseerd op het idee dat de priemgetallen zijn gerangschikt van klein naar groot (bijvoorbeeld 2 is het eerste priemgetal, 3 is het tweede priemgetal, en 101 is de 26 ^e prime). Het is ook mogelijk om de vierkantswortel van een willekeurig getal te nemen, en vergelijk het resultaat met het dichtstbijzijnde priemgetal. Bijvoorbeeld, de vierkantswortel van 27 is iets meer dan 5, wat het derde priemgetal is. Volgens de definitie van een factorisatie-ensemble, dit betekent dat 27 behoort tot het factorisatie-ensemble van 3.

De natuurkundigen toonden vervolgens aan dat ze de factorisatie-ensemblefunctie konden transformeren in een functie uit de kwantumfysica (de omgekeerde harmonische-oscillatorfunctie). Na nog veel meer stappen, ze toonden uiteindelijk aan dat het voorspelde energiespectrum van een kwantumsysteem overeenkomt met de verdeling van priemgetallen in het factorisatie-ensemble van een getal. Uit deze informatie, de onderzoekers kunnen de kans bepalen dat een priemgetal een factor is van dat getal. Om de validiteit van hun methode te testen, de natuurkundigen hebben bepaalde getallen getest en hun resultaten vergeleken met de werkelijke verdelingen die zijn verkregen met behulp van priemgetaltabellen, en vond zeer vergelijkbare distributies.

De natuurkundigen hebben theoretisch aangetoond dat de voorgestelde kwantumsimulator getallen kan factoriseren die vele ordes van grootte groter zijn dan die waarmee met kwantumcomputers rekening is gehouden. In hun krant ze rapporteren de resultaten van het gebruik van hun methode om de kansverdeling van de priemfactoren van een getal met 24 cijfers te bepalen. Verder, de methode doet dit met veel minder middelen dan vereist door klassieke factoringalgoritmen.

"In de kwantumtheorie de algoritmische complexiteit is alleen polynoom met het aantal bits van het getal dat moet worden ontbonden, ' zei Rosales. 'Eigenlijk, onze eerste resultaten lijken te bevestigen dat de simulator alleen (log√N) nodig heeft ³ kwantumtoestanden om het spectrum van energieën te reproduceren, een zeer bemoedigend resultaat."

Een laatste aandachtspunt is dat de nieuwe methode sterke connecties heeft met de Riemann-hypothese, die, als het waar is, zou suggereren dat de priemgetallen op een voorspelbare manier worden verdeeld - op dezelfde manier als de verdeling van de nullen van de Riemann-zeta-functie. Het bewijzen (of weerleggen) van de Riemann-hypothese is een van de grootste onopgeloste problemen in de wiskunde, en een van de Millenniumprijsproblemen van het Clay Mathematics Institute.

"De priemgetallen zouden zich als kwantumgetallen moeten gedragen als het vermoeden van Hilbert-Polya van toepassing is, " zei Rosales, verwijzend naar de al lang bestaande benadering om de Riemann-hypothese te bewijzen.

Vooruit gaan, de onderzoekers werken momenteel aan de experimentele implementatie van de kwantumsimulator door twee verstrengelde deeltjes in een Penning-val te gebruiken.

"De volledige kwantumbehandeling van de simulator zou een kwantumoptische analyse vereisen van de interacties van fotonen met twee (of meer) verstrengelde ionen in een Penning-val, "Zei Rosales. "Dit deel van het programma is nog in ontwikkeling. Het doel is om experimenteel een quantumfactoringsimulator te bouwen. Indien succesvol geïmplementeerd, getallen die vele orden van grootte groter zijn dan die beschikbaar zijn voor de kwantumverwerking met behulp van Shor's algoritme, zullen worden ontbonden en, als bijproduct, het vermoeden van Hilbert-Polya zal experimenteel worden getest."

© 2018 Fys.org