Faktorizace pomocí Gaussovských sum: chování nepravých dělitelů

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F07%3A04134308" target="_blank" >RIV/68407700:21340/07:04134308 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Gauss Sum Factorization: Scaling Properties of Ghost Factors

Popis výsledku v původním jazyce

Recent experiments have shown that truncated Gauss sums allow us to find the factors of an integer N. This method relies on the fact that for a factor the absolute value of the Gauss sum is unity. However, for every integer N there exist integers which are not factors, but where the Gauss sum reaches a value which is arbitrarily close to unity. In order to distinguish such ghost factors from real factors we need to amplify this difference. We show, that a proper choice of the truncation parameter of theGauss sum suppresses the ghost factors below a threshold value. We derive the scaling law of the truncation parameter on the number to be factored. Moreover, we show that this scaling law is also necessary for the success of our factorization scheme, even if we relax the threshold or allow limited error tolerance.

Název v anglickém jazyce

Gauss Sum Factorization: Scaling Properties of Ghost Factors

Popis výsledku anglicky

Recent experiments have shown that truncated Gauss sums allow us to find the factors of an integer N. This method relies on the fact that for a factor the absolute value of the Gauss sum is unity. However, for every integer N there exist integers which are not factors, but where the Gauss sum reaches a value which is arbitrarily close to unity. In order to distinguish such ghost factors from real factors we need to amplify this difference. We show, that a proper choice of the truncation parameter of theGauss sum suppresses the ghost factors below a threshold value. We derive the scaling law of the truncation parameter on the number to be factored. Moreover, we show that this scaling law is also necessary for the success of our factorization scheme, even if we relax the threshold or allow limited error tolerance.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BE - Teoretická fyzika

OECD FORD obor

—

Projekt

<a href="/cs/project/LC06002" target="_blank" >LC06002: Dopplerův ústav pro matematickou fyziku a aplikovanou matematiku</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2007

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

New Journal of Physics

ISSN

1367-2630

e-ISSN

—

Svazek periodika

9

Číslo periodika v rámci svazku

—

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

18

Strana od-do

370-0

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—