Post Reply 
Square Root Modulo An Odd Prime Programme
02-26-2016, 08:10 AM
Post: #1
Square Root Modulo An Odd Prime Programme
The programme MSQRT finds the modulo square root of a positive integer for a prime modulus.

eg For input

18081955
9999999929

where 9999999929 is the prime modulus (the largest prime < 10^10 & = 1 mod 4)

the programme returns

1058134345

to the stack.

The programme calls various sub-programmes.

SQM finds the square modulo the prime modulus:

Code:

1.  ►LBL  SQM
2.    STO Y
3.    1E5
4.    MOD
5.    STO Z
6.    –
7.    ENTER
8.    X^2
9.    RCL 00
10.    MOD
11.    X<>Y
12.    R↑
13.    ST* T
14.    *
15.    RCL 01
16.    MOD
17.    RCL 00
18.    X<>Y
19.    +
20.    LASTX
21.    +
22.    RCL 01
23.    MOD
24.    +
25.    RCL 00
26.    MOD
27.    +
28.    RCL 01
29.    MOD
30.    END

M* multiplies two integers modulo the modulus:

Code:

1.  ►LBL  M*
2.    STO 09
3.    X<>Y
4.    ENTER
5.    ENTER
6.    1E5
7.    MOD
8.    STO 05
9.    –
10.    STO 06
11.    RCL 09
12.    ENTER
13.    ENTER
14.    1E5
15.    MOD
16.    STO 07
17.    –
18.    STO 08
19.    RCL 06
20.    *
21.    RCL 00
22.    MOD
23.    RCL 08
24.    RCL 05
25.    *
26.    RCL 01
27.    MOD
28.    +
29.    RCL 00
30.    MOD
31.    RCL 06
32.    RCL 07
33.    *
34.    RCL 01
35.    MOD
36.    +
37.    RCL 00
38.    MOD
39.    RCL 07
40.    RCL 05
41.    *
42.    +
43.    RCL 01
44.    MOD
45.    STO 09
46.    END

M↑ calculates the x stack level power of the y stack level modulo the modulus:

Code:

1.  ►LBL  M↑
2.    STO 02
3.    RDN
4.    STO 03
5.    SIGN
6.    GTO 00
7.    ►LBL  01
8.    2
9.    MOD
10.    X≠0?
11.    GTO 02
12.    LASTX
13.    STO/ 02
14.    RCL 03
15.    XEQ SQM
16.    STO 03
17.    RCL 02
18.    GTO 01
19.    ►LBL  02
20.    STO- 02
21.    RCL 04
22.    RCL 03
23.    XEQ M*
24.    ►LBL  00
25.    STO 04
26.    RCL 02
27.    X≠0?
28.    GTO 01
29.    RDN
30.    END

KRON is a stand alone programme to find the Kronecker sign of stack level y with respect to stack level x, ie whether y is a quadratic residue of x:

Code:

1.  ►LBL  KRON
2.    X=0?
3.    GTO 00
4.    STO 04
5.    X<>Y
6.    STO 02
7.    2
8.    MOD
9.    X<>Y
10.    LASTX
11.    MOD
12.    +
13.    X=0?
14.    RTN
15.    SIGN
16.    STO 03
17.    CLX
18.    XEQ 01
19.    RCL 02
20.    X<> 04
21.    STO 02
22.    X<0?
23.    GTO 05
24.    GTO 03
25.    ►LBL  05
26.    ABS
27.    STO 02
28.    RCL 04
29.    SIGN
30.    STO* 03
31.    ►LBL  03
32.    RCL 04
33.    X=0?
34.    GTO 04
35.    CLX
36.    XEQ 01
37.    RCL 04
38.    4
39.    MOD
40.    RCL 02
41.    LASTX
42.    MOD
43.    *
44.    9
45.    X=Y?
46.    CHS
47.    SIGN
48.    STO* 03
49.    RCL 04
50.    ABS
51.    ENTER
52.    X<> 02
53.    X<>Y
54.    MOD
55.    STO 04
56.    GTO 03
57.    ►LBL  01
58.    RCL 04
59.    2
60.    MOD
61.    X≠0?
62.    GTO 02
63.    2
64.    STO/ 04
65.    RCL Z
66.    1
67.    +
68.    CHS
69.    GTO 01
70.    ►LBL  02
71.    RDN
72.    X=0?
73.    RTN
74.    RCL 02
75.    8
76.    MOD
77.    4
78.    –
79.    ABS
80.    1
81.    X=Y?
82.    CHS
83.    STO* 03
84.    RTN
85.    ►LBL  04
86.    RCL 02
87.    1
88.    X≠Y?
89.    0
90.    RCL 03
91.    *
92.    RTN
93.    ►LBL  00
94.    RDN
95.    ABS
96.    1
97.    X≠Y?
98.    CLX
99.    END

& finally MSQRT:

Code:

1.  ►LBL  MSQRT
2.    CHS
3.    STO 00
4.    CHS
5.    STO 01
6.    MOD
7.    ENTER
8.    SQRT
9.    ENTER
10.    FRC
11.    X≠0?
12.    GTO 07
13.    RDN
14.    RTN
15.    ►LBL  07
16.    RCL Z
17.    STO 13
18.    RCL 01
19.    XEQ KRON
20.    1
21.    +
22.    X=0?
23.    RTN
24.    RCL 01
25.    4
26.    MOD
27.    1
28.    –
29.    X=0?
30.    GTO 08
31.    RCL 13
32.    RCL 01
33.    1
34.    +
35.    4
36.    /
37.    XEQ M↑
38.    RTN
39.    ►LBL  08
40.    STO 14
41.    RCL 01
42.    DSE X
43.    ►LBL  00
44.    STO Y
45.    2
46.    MOD
47.    X≠0?
48.    GTO 01
49.    RDN
50.    LASTX
51.    /
52.    ISG 14
53.    CLA
54.    GTO 00
55.    ►LBL  01
56.    RDN
57.    STO 15
58.    1
59.    STO 16
60.    ►LBL  02
61.    1
62.    STO+ 16
63.    RCL 16
64.    RCL 01
65.    XEQ KRON
66.    X>0?
67.    GTO 02
68.    RCL 16
69.    RCL 15
70.    XEQ M↑
71.    STO 17
72.    RCL 14
73.    STO 16
74.    RCL 13
75.    –1
76.    RCL 15
77.    +
78.    2
79.    /
80.    XEQ M↑
81.    STO 18
82.    RCL 13
83.    XEQ M*
84.    ENTER
85.    X<> 18
86.    XEQ M*
87.    ►LBL  04
88.    STO 13
89.    1
90.    X=Y?
91.    GTO 05
92.    STO 14
93.    RDN
94.    ►LBL  06
95.    XEQ SQM
96.    1
97.    X=Y?
98.    GTO 03
99.    STO+ 14
100.    RDN
101.    GTO 06
102.    ►LBL  03
103.    RCL 17
104.    2
105.    RCL 16
106.    RCL 14
107.    -
108.    1
109.    –
110.    Y^X
111.    XEQ M↑
112.    XEQ SQM
113.    STO 17
114.    RCL 14
115.    STO 16
116.    RCL 18
117.    RCL 04
118.    XEQ M*
119.    STO 18
120.    RCL 13
121.    RCL 17
122.    XEQ M*
123.    GTO 04
124.    ►LBL  05
125.    RCL 18
126.    END
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)