Shanks's square forms factorization: Difference between revisions

Revision as of 04:06, 30 October 2023

Revision as of 04:13, 30 October 2023

Line 16:

'''The algorithm:'''

Initialize <math>i=0,P_0=\lfloor\sqrt{kN}\rfloor,Q_0Q_{-1}=1,Q_1Q_0=kN-P_0^2.</math>

Repeat

<math>i=i+1,b_i=\left\lfloor\frac{P_0+P_{i-1}}{Q_iQ_{i-1}}\right\rfloor,P_i=b_iQ_i-P_b_iQ_{i-1},Q_-P_{i+-1},Q_i=Q_{i-12}+b_i(P_{i-1}-P_i)</math>

until <math>Q_{i+1}Q_i</math> is a perfect square at some odd value of <math>i</math>.

Start the second phase (reverse cycle).

Initialize <math>b_0=\left\lfloor\frac{P_0-P_i}{\sqrt{Q_{i+1}Q_i}}\right\rfloor</math>, <math>Q_{-1}=\sqrt{Q_{i+1}Q_i}</math>, and <math>P_0=b_0\sqrt{Q_{i+1}Q_i}+P_i</math>, where <math>P_0, P_i</math>, and <math>Q_{i+1}</math> are from the previous phase. The <math>b_0</math> used in the calculation of <math>P_0</math> is the recently calculated value of <math>b_0</math>.

Set <math> i=0</math> and <math> Q_0=\frac{kN-P_0^2}{Q_{-1}}</math>, where <math>P_0</math> is the recently calculated value of <math>P_0</math>.