Gauss Sum Factorization: Scaling Properties of Ghost Factors

Result code in 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>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Gauss Sum Factorization: Scaling Properties of Ghost Factors

Original language description

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.

Czech name

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

Czech description

Nedávné experimenty ukázaly, že zkrácené Gaussovské sumy umožňují nalézt dělitele daného celého čísla N. Tato metoda je založena na faktu že pouze pro dělitele je absolutní hodnota Gaussovy sumy rovna jedné. Nicméně, pro každé celé číslo N existují nedělitele, pro které je hodnota Gaussovy sumy libovolně blízko jedné. Abychom mohli odlišit tyto nepravé dělitele od skutečných musíme zvětšit tento rozdíl. Ukážeme, že vhodná volba parametru M, který určuje délku Gaussovské sumy, nám umožní potlačit všechnynepravé dělitele pod danou mez. Najdeme zavislost parametru M na čísle N jehož dělitele hledáme. Navíc ukážeme, že tato volba M je nezbytná pro nalezení dělitelů N, i v případě že tolerujeme omezené množství chyb.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BE - Theoretical physics

OECD FORD branch

—

Project

<a href="/en/project/LC06002" target="_blank" >LC06002: Doppler Institute for Mathematical Physics and Applied Mathematics</a><br>

Continuities

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

Publication year

2007

Confidentiality

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

Name of the periodical

New Journal of Physics

ISSN

1367-2630

e-ISSN

—

Volume of the periodical

9

Issue of the periodical within the volume

—

Country of publishing house

GB - UNITED KINGDOM

Number of pages

18

Pages from-to

370-0

UT code for WoS article

—

EID of the result in the Scopus database

—