On factoring large numbers. (Q572065): Difference between revisions

Kennt man für eine Zahl \(N\) eine Kongruenz der Form \[ u^2 \equiv v^2 \;(\text{mod } N), \] so erhält man, falls weder \(u + v\) noch \(u - v\) durch \(N\) teilbar sind, durch Bestimmung des größten gemeinsamen Teilers von \(u + v\) (oder \(u - v\)) und \(N\) eine Faktorzerlegung von \(N\). Verf. geben zur Gewinnung von Kongruenzen der obigen Form zwei Methoden an, die auf der Kettenbruchentwicklung von \(\sqrt N\) beruhen.