fork(1) download
  1. import math
  2.  
  3. def modular_sqrt(a, p):
  4. """ Find a quadratic residue (mod p) of 'a'. p
  5. must be an odd prime.
  6.  
  7. Solve the congruence of the form:
  8. x^2 = a (mod p)
  9. And returns x. Note that p - x is also a root.
  10.  
  11. 0 is returned is no square root exists for
  12. these a and p.
  13.  
  14. The Tonelli-Shanks algorithm is used (except
  15. for some simple cases in which the solution
  16. is known from an identity). This algorithm
  17. runs in polynomial time (unless the
  18. generalized Riemann hypothesis is false).
  19. """
  20. # Simple cases
  21. #
  22. if legendre_symbol(a, p) != 1:
  23. return 0
  24. elif a == 0:
  25. return 0
  26. elif p == 2:
  27. return 0
  28. elif p % 4 == 3:
  29. return pow(a, (p + 1) // 4, p)
  30.  
  31. # Partition p-1 to s * 2^e for an odd s (i.e.
  32. # reduce all the powers of 2 from p-1)
  33. #
  34. s = p - 1
  35. e = 0
  36. while s % 2 == 0:
  37. s //= 2
  38. e += 1
  39.  
  40. # Find some 'n' with a legendre symbol n|p = -1.
  41. # Shouldn't take long.
  42. #
  43. n = 2
  44. while legendre_symbol(n, p) != -1:
  45. n += 1
  46.  
  47. # Here be dragons!
  48. # Read the paper "Square roots from 1; 24, 51,
  49. # 10 to Dan Shanks" by Ezra Brown for more
  50. # information
  51. #
  52.  
  53. # x is a guess of the square root that gets better
  54. # with each iteration.
  55. # b is the "fudge factor" - by how much we're off
  56. # with the guess. The invariant x^2 = ab (mod p)
  57. # is maintained throughout the loop.
  58. # g is used for successive powers of n to update
  59. # both a and b
  60. # r is the exponent - decreases with each update
  61. #
  62. x = pow(a, (s + 1) // 2, p)
  63. b = pow(a, s, p)
  64. g = pow(n, s, p)
  65. r = e
  66.  
  67. while True:
  68. t = b
  69. m = 0
  70. for m in range(r):
  71. if t == 1:
  72. break
  73. t = pow(t, 2, p)
  74.  
  75. if m == 0:
  76. return x
  77.  
  78. gs = pow(g, 2 ** (r - m - 1), p)
  79. g = (gs * gs) % p
  80. x = (x * gs) % p
  81. b = (b * g) % p
  82. r = m
  83.  
  84.  
  85. def legendre_symbol(a, p):
  86. """ Compute the Legendre symbol a|p using
  87. Euler's criterion. p is a prime, a is
  88. relatively prime to p (if p divides
  89. a, then a|p = 0)
  90.  
  91. Returns 1 if a has a square root modulo
  92. p, -1 otherwise.
  93. """
  94. ls = pow(a, (p - 1) // 2, p)
  95. return -1 if ls == p - 1 else ls
  96.  
  97. def inverse(x, p):
  98. return pow(x, p - 2, p)
  99.  
  100. def solve(p):
  101. # solve 3 n^2 + 3 n + 1 ≡ 0
  102. D = -3 % p
  103. sqrtD = modular_sqrt(D, p)
  104. if sqrtD == 0:
  105. return None
  106. else:
  107. n = (sqrtD - 3) * inverse(6, p) % p
  108. return (n, -(n+1) % p)
  109.  
  110. def is_prime(n):
  111. return not any(n % p == 0 for p in range(2, int(math.sqrt(n)) + 1))
  112.  
  113. for P in range(5, 10000, 2):
  114. if not(is_prime(P)):
  115. continue
  116.  
  117. s = solve(P)
  118. if s == None:
  119. print(P, "None")
  120. else:
  121. (s0, s1) = s
  122. print(P, s0, s1)
  123. if pow(s0, 3, P) != pow(s0 + 1, 3, P) or pow(s1, 3, P) != pow(s1 + 1, 3, P):
  124. print("Wrong")
Success #stdin #stdout 0.05s 27952KB
stdin
Standard input is empty
stdout
5 None
7 1 5
11 None
13 5 7
17 None
19 16 2
23 None
29 None
31 8 22
37 33 3
41 None
43 16 26
47 None
53 None
59 None
61 56 4
67 54 12
71 None
73 51 21
79 18 60
83 None
89 None
97 20 76
101 None
103 15 87
107 None
109 51 57
113 None
127 120 6
131 None
137 None
139 78 60
149 None
151 39 111
157 100 56
163 143 19
167 None
173 None
179 None
181 76 104
191 None
193 100 92
197 None
199 35 163
211 65 145
223 135 87
227 None
229 31 197
233 None
239 None
241 155 85
251 None
257 None
263 None
269 None
271 9 261
277 53 223
281 None
283 203 79
293 None
307 96 210
311 None
313 71 241
317 None
331 320 10
337 267 69
347 None
349 273 75
353 None
359 None
367 94 272
373 29 343
379 143 235
383 None
389 None
397 11 385
401 None
409 118 290
419 None
421 287 133
431 None
433 222 210
439 203 235
443 None
449 None
457 412 44
461 None
463 161 301
467 None
479 None
487 77 409
491 None
499 46 452
503 None
509 None
521 None
523 194 328
541 317 223
547 13 533
557 None
563 None
569 None
571 36 534
577 263 313
587 None
593 None
599 None
601 392 208
607 334 272
613 430 182
617 None
619 290 328
631 616 14
641 None
643 273 369
647 None
653 None
659 None
661 121 539
673 309 363
677 None
683 None
691 606 84
701 None
709 548 160
719 None
727 578 148
733 630 102
739 599 139
743 None
751 476 274
757 261 495
761 None
769 376 392
773 None
787 660 126
797 None
809 None
811 43 767
821 None
823 332 490
827 None
829 594 234
839 None
853 779 73
857 None
859 659 199
863 None
877 386 490
881 None
883 770 112
887 None
907 476 430
911 None
919 17 901
929 None
937 829 107
941 None
947 None
953 None
967 919 47
971 None
977 None
983 None
991 698 292
997 895 101
1009 797 211
1013 None
1019 None
1021 803 217
1031 None
1033 409 623
1039 739 299
1049 None
1051 410 640
1061 None
1063 948 114
1069 327 741
1087 276 810
1091 None
1093 1042 50
1097 None
1103 None
1109 None
1117 412 704
1123 385 737
1129 623 505
1151 None
1153 985 167
1163 None
1171 530 640
1181 None
1187 None
1193 None
1201 590 610
1213 1140 72
1217 None
1223 None
1229 None
1231 778 452
1237 512 724
1249 801 447
1259 None
1277 None
1279 594 684
1283 None
1289 None
1291 1175 115
1297 986 310
1301 None
1303 900 402
1307 None
1319 None
1321 539 781
1327 326 1000
1361 None
1367 None
1373 None
1381 578 802
1399 802 596
1409 None
1423 214 1208
1427 None
1429 221 1207
1433 None
1439 None
1447 247 1199
1451 None
1453 715 737
1459 599 859
1471 406 1064
1481 None
1483 481 1001
1487 None
1489 831 657
1493 None
1499 None
1511 None
1523 None
1531 215 1315
1543 741 801
1549 424 1124
1553 None
1559 None
1567 1388 178
1571 None
1579 739 839
1583 None
1597 990 606
1601 None
1607 None
1609 1525 83
1613 None
1619 None
1621 1559 61
1627 630 996
1637 None
1657 23 1633
1663 660 1002
1667 None
1669 473 1195
1693 144 1548
1697 None
1699 132 1566
1709 None
1721 None
1723 560 1162
1733 None
1741 1279 461
1747 1288 458
1753 1229 523
1759 169 1589
1777 1394 382
1783 64 1718
1787 None
1789 1243 545
1801 1776 24
1811 None
1823 None
1831 834 996
1847 None
1861 151 1709
1867 900 966
1871 None
1873 1210 662
1877 None
1879 463 1415
1889 None
1901 None
1907 None
1913 None
1931 None
1933 1091 841
1949 None
1951 25 1925
1973 None
1979 None
1987 446 1540
1993 1224 768
1997 None
1999 1729 269
2003 None
2011 1942 68
2017 1246 770
2027 None
2029 1001 1027
2039 None
2053 1434 618
2063 None
2069 None
2081 None
2083 1538 544
2087 None
2089 1813 275
2099 None
2111 None
2113 1262 850
2129 None
2131 1264 866
2137 1357 779
2141 None
2143 2026 116
2153 None
2161 1638 522
2179 1411 767
2203 829 1373
2207 None
2213 None
2221 1299 921
2237 None
2239 98 2140
2243 None
2251 1264 986
2267 None
2269 2241 27
2273 None
2281 1299 981
2287 1256 1030
2293 434 1858
2297 None
2309 None
2311 1246 1064
2333 None
2339 None
2341 411 1929
2347 1210 1136
2351 None
2357 None
2371 635 1735
2377 2136 240
2381 None
2383 426 1956
2389 1822 566
2393 None
2399 None
2411 None
2417 None
2423 None
2437 28 2408
2441 None
2447 None
2459 None
2467 1572 894
2473 338 2134
2477 None
2503 425 2077
2521 1065 1455
2531 None
2539 948 1590
2543 None
2549 None
2551 833 1717
2557 278 2278
2579 None
2591 None
2593 1243 1349
2609 None
2617 517 2099
2621 None
2633 None
2647 1826 820
2657 None
2659 1471 1187
2663 None
2671 181 2489
2677 2332 344
2683 1576 1106
2687 None
2689 2558 130
2693 None
2699 None
2707 2264 442
2711 None
2713 2212 500
2719 484 2234
2729 None
2731 1969 761
2741 None
2749 198 2550
2753 None
2767 2657 109
2777 None
2789 None
2791 2760 30
2797 565 2231
2801 None
2803 796 2006
2819 None
2833 2399 433
2837 None
2843 None
2851 1288 1562
2857 835 2021
2861 None
2879 None
2887 729 2157
2897 None
2903 None
2909 None
2917 82 2834
2927 None
2939 None
2953 717 2235
2957 None
2963 None
2969 None
2971 1008 1962
2999 None
3001 2689 311
3011 None
3019 2092 926
3023 None
3037 248 2788
3041 None
3049 2871 177
3061 1207 1853
3067 324 2742
3079 1870 1208
3083 None
3089 None
3109 2434 674
3119 None
3121 666 2454
3137 None
3163 2287 875
3167 None
3169 32 3136
3181 913 2267
3187 438 2748
3191 None
3203 None
3209 None
3217 1140 2076
3221 None
3229 771 2457
3251 None
3253 2648 604
3257 None
3259 1370 1888
3271 809 2461
3299 None
3301 2725 575
3307 1121 2185
3313 2938 374
3319 1615 1703
3323 None
3329 None
3331 2708 622
3343 2703 639
3347 None
3359 None
3361 297 3063
3371 None
3373 1342 2030
3389 None
3391 2075 1315
3407 None
3413 None
3433 3343 89
3449 None
3457 911 2545
3461 None
3463 122 3340
3467 None
3469 1751 1717
3491 None
3499 2280 1218
3511 1422 2088
3517 1258 2258
3527 None
3529 3379 149
3533 None
3539 None
3541 2380 1160
3547 3159 387
3557 None
3559 3080 478
3571 3536 34
3581 None
3583 2042 1540
3593 None
3607 466 3140
3613 558 3054
3617 None
3623 None
3631 2532 1098
3637 980 2656
3643 1073 2569
3659 None
3671 None
3673 840 2832
3677 None
3691 1388 2302
3697 2291 1405
3701 None
3709 1402 2306
3719 None
3727 1638 2088
3733 2172 1560
3739 231 3507
3761 None
3767 None
3769 154 3614
3779 None
3793 1620 2172
3797 None
3803 None
3821 None
3823 2943 879
3833 None
3847 651 3195
3851 None
3853 2948 904
3863 None
3877 1217 2659
3881 None
3889 1926 1962
3907 1281 2625
3911 None
3917 None
3919 916 3002
3923 None
3929 None
3931 2826 1104
3943 378 3564
3947 None
3967 2348 1618
3989 None
4001 None
4003 1608 2394
4007 None
4013 None
4019 None
4021 2076 1944
4027 735 3291
4049 None
4051 1084 2966
4057 469 3587
4073 None
4079 None
4091 None
4093 3029 1063
4099 3426 672
4111 1018 3092
4127 None
4129 716 3412
4133 None
4139 None
4153 2825 1327
4157 None
4159 3307 851
4177 367 3809
4201 3175 1025
4211 None
4217 None
4219 37 4181
4229 None
4231 3027 1203
4241 None
4243 99 4143
4253 None
4259 None
4261 2291 1969
4271 None
4273 3385 887
4283 None
4289 None
4297 2394 1902
4327 1651 2675
4337 None
4339 2813 1525
4349 None
4357 3917 439
4363 4225 137
4373 None
4391 None
4397 None
4409 None
4421 None
4423 1496 2926
4441 300 4140
4447 4408 38
4451 None
4457 None
4463 None
4481 None
4483 168 4314
4493 None
4507 3268 1238
4513 4241 271
4517 None
4519 2660 1858
4523 None
4547 None
4549 581 3967
4561 2959 1601
4567 1151 3415
4583 None
4591 4487 103
4597 1406 3190
4603 3128 1474
4621 952 3668
4637 None
4639 4185 453
4643 None
4649 None
4651 1812 2838
4657 4334 322
4663 697 3965
4673 None
4679 None
4691 None
4703 None
4721 None
4723 2909 1813
4729 3831 897
4733 None
4751 None
4759 4250 508
4783 3770 1012
4787 None
4789 1036 3752
4793 None
4799 None
4801 2420 2380
4813 4183 629
4817 None
4831 1633 3197
4861 106 4754
4871 None
4877 None
4889 None
4903 805 4097
4909 1827 3081
4919 None
4931 None
4933 710 4222
4937 None
4943 None
4951 4054 896
4957 891 4065
4967 None
4969 3250 1718
4973 None
4987 3703 1283
4993 4109 883
4999 2553 2445
5003 None
5009 None
5011 2371 2639
5021 None
5023 3666 1356
5039 None
5051 None
5059 4421 637
5077 2235 2841
5081 None
5087 None
5099 None
5101 2238 2862
5107 1598 3508
5113 1680 3432
5119 1145 3973
5147 None
5153 None
5167 41 5125
5171 None
5179 2225 2953
5189 None
5197 2838 2358
5209 397 4811
5227 150 5076
5231 None
5233 110 5122
5237 None
5261 None
5273 None
5279 None
5281 3988 1292
5297 None
5303 None
5309 None
5323 427 4895
5333 None
5347 3724 1622
5351 None
5381 None
5387 None
5393 None
5399 None
5407 5059 347
5413 3200 2212
5417 None
5419 5376 42
5431 2321 3109
5437 2867 2569
5441 None
5443 4491 951
5449 491 4957
5471 None
5477 None
5479 925 4553
5483 None
5501 None
5503 1524 3978
5507 None
5519 None
5521 113 5407
5527 3392 2134
5531 None
5557 2461 3095
5563 2091 3471
5569 747 4821
5573 None
5581 819 4761
5591 None
5623 3077 2545
5639 None
5641 4959 681
5647 5362 284
5651 None
5653 4015 1637
5657 None
5659 3284 2374
5669 None
5683 2264 3418
5689 4882 806
5693 None
5701 1925 3775
5711 None
5717 None
5737 3001 2735
5741 None
5743 1847 3895
5749 2026 3722
5779 4828 950
5783 None
5791 2454 3336
5801 None
5807 None
5813 None
5821 2656 3164
5827 2392 3434
5839 2564 3274
5843 None
5849 None
5851 5658 192
5857 5435 421
5861 None
5867 None
5869 3653 2215
5879 None
5881 3828 2052
5897 None
5903 None
5923 1831 4091
5927 None
5939 None
5953 4258 1694
5981 None
5987 None
6007 1976 4030
6011 None
6029 None
6037 1842 4194
6043 1442 4600
6047 None
6053 None
6067 4266 1800
6073 2638 3434
6079 1508 4570
6089 None
6091 2278 3812
6101 None
6113 None
6121 2424 3696
6131 None
6133 316 5816
6143 None
6151 4031 2119
6163 2080 4082
6173 None
6197 None
6199 5014 1184
6203 None
6211 45 6165
6217 1252 4964
6221 None
6229 2386 3842
6247 3392 2854
6257 None
6263 None
6269 None
6271 5597 673
6277 769 5507
6287 None
6299 None
6301 992 5308
6311 None
6317 None
6323 None
6329 None
6337 3720 2616
6343 1928 4414
6353 None
6359 None
6361 619 5741
6367 256 6110
6373 1916 4456
6379 3128 3250
6389 None
6397 1367 5029
6421 5315 1105
6427 361 6065
6449 None
6451 4371 2079
6469 2648 3820
6473 None
6481 4347 2133
6491 None
6521 None
6529 2012 4516
6547 5769 777
6551 None
6553 2832 3720
6563 None
6569 None
6571 3387 3183
6577 2074 4502
6581 None
6599 None
6607 2708 3898
6619 2016 4602
6637 4881 1755
6653 None
6659 None
6661 449 6211
6673 464 6208
6679 2540 4138
6689 None
6691 5433 1257
6701 None
6703 6209 493
6709 2649 4059
6719 None
6733 6526 206
6737 None
6761 None
6763 718 6044
6779 None
6781 5805 975
6791 None
6793 389 6403
6803 None
6823 3169 3653
6827 None
6829 2031 4797
6833 None
6841 3624 3216
6857 None
6863 None
6869 None
6871 1801 5069
6883 2367 4515
6899 None
6907 5223 1683
6911 None
6917 None
6947 None
6949 6301 647
6959 None
6961 4471 2489
6967 127 6839
6971 None
6977 None
6983 None
6991 460 6530
6997 969 6027
7001 None
7013 None
7019 None
7027 174 6852
7039 4793 2245
7043 None
7057 48 7008
7069 3036 4032
7079 None
7103 None
7109 None
7121 None
7127 None
7129 6712 416
7151 None
7159 3346 3812
7177 679 6497
7187 None
7193 None
7207 1789 5417
7211 None
7213 867 6345
7219 6310 908
7229 None
7237 4214 3022
7243 3686 3556
7247 None
7253 None
7283 None
7297 6118 1178
7307 None
7309 6011 1297
7321 2337 4983
7331 None
7333 1423 5909
7349 None
7351 49 7301
7369 4059 3309
7393 572 6820
7411 7279 131
7417 5715 1701
7433 None
7451 None
7457 None
7459 2562 4896
7477 3828 3648
7481 None
7487 None
7489 6666 822
7499 None
7507 2704 4802
7517 None
7523 None
7529 None
7537 3166 4370
7541 None
7547 None
7549 4856 2692
7559 None
7561 5473 2087
7573 5734 1838
7577 None
7583 None
7589 None
7591 5878 1712
7603 3232 4370
7607 None
7621 1041 6579
7639 6084 1554
7643 None
7649 None
7669 4422 3246
7673 None
7681 2788 4892
7687 3320 4366
7691 None
7699 6942 756
7703 None
7717 6570 1146
7723 5454 2268
7727 None
7741 817 6923
7753 134 7618
7757 None
7759 586 7172
7789 2518 5270
7793 None
7817 None
7823 None
7829 None
7841 None
7853 None
7867 488 7378
7873 2159 5713
7877 None
7879 7423 455
7883 None
7901 None
7907 None
7919 None
7927 4031 3895
7933 7264 668
7937 None
7949 None
7951 5193 2757
7963 4767 3195
7993 1081 6911
8009 None
8011 2640 5370
8017 6225 1791
8039 None
8053 6534 1518
8059 1764 6294
8069 None
8081 None
8087 None
8089 3167 4921
8093 None
8101 3439 4661
8111 None
8117 None
8123 None
8147 None
8161 6408 1752
8167 6475 1691
8171 None
8179 365 7813
8191 2760 5430
8209 7120 1088
8219 None
8221 138 8082
8231 None
8233 1873 6359
8237 None
8243 None
8263 5428 2834
8269 52 8216
8273 None
8287 8097 189
8291 None
8293 7609 683
8297 None
8311 3192 5118
8317 2343 5973
8329 2425 5903
8353 2205 6147
8363 None
8369 None
8377 5313 3063
8387 None
8389 8158 230
8419 6266 2152
8423 None
8429 None
8431 2094 6336
8443 3159 5283
8447 None
8461 5048 3412
8467 7040 1426
8501 None
8513 None
8521 6355 2165
8527 4692 3834
8537 None
8539 6543 1995
8543 None
8563 4767 3795
8573 None
8581 141 8439
8597 None
8599 2464 6134
8609 None
8623 5233 3389
8627 None
8629 4650 3978
8641 6951 1689
8647 6029 2617
8663 None
8669 None
8677 8217 459
8681 None
8689 634 8054
8693 None
8699 None
8707 804 7902
8713 2058 6654
8719 7958 760
8731 7511 1219
8737 3668 5068
8741 None
8747 None
8753 None
8761 6418 2342
8779 8356 422
8783 None
8803 329 8473
8807 None
8819 None
8821 5068 3752
8831 None
8837 None
8839 1457 7381
8849 None
8861 None
8863 5421 3441
8867 None
8887 4371 4515
8893 5845 3047
8923 7640 1282
8929 7482 1446
8933 None
8941 2433 6507
8951 None
8963 None
8969 None
8971 6094 2876
8999 None
9001 4266 4734
9007 6369 2637
9011 None
9013 7904 1108
9029 None
9041 None
9043 7079 1963
9049 2734 6314
9059 None
9067 360 8706
9091 7961 1129
9103 1574 7528
9109 5032 4076
9127 8123 1003
9133 1778 7354
9137 None
9151 6492 2658
9157 8725 431
9161 None
9173 None
9181 336 8844
9187 1688 7498
9199 7388 1810
9203 None
9209 None
9221 None
9227 None
9239 None
9241 55 9185
9257 None
9277 200 9076
9281 None
9283 2146 7136
9293 None
9311 None
9319 5166 4152
9323 None
9337 1466 7870
9341 None
9343 7305 2037
9349 4456 4892
9371 None
9377 None
9391 2802 6588
9397 7139 2257
9403 7405 1997
9413 None
9419 None
9421 5487 3933
9431 None
9433 6597 2835
9437 None
9439 244 9194
9461 None
9463 202 9260
9467 None
9473 None
9479 None
9491 None
9497 None
9511 1163 8347
9521 None
9533 None
9539 None
9547 1089 8457
9551 None
9587 None
9601 4602 4998
9613 2175 7437
9619 1475 8143
9623 None
9629 None
9631 9090 540
9643 4746 4896
9649 1138 8510
9661 5889 3771
9677 None
9679 4197 5481
9689 None
9697 7128 2568
9719 None
9721 641 9079
9733 2727 7005
9739 2323 7415
9743 None
9749 None
9767 None
9769 6425 3343
9781 7956 1824
9787 8776 1010
9791 None
9803 None
9811 3069 6741
9817 318 9498
9829 9579 249
9833 None
9839 None
9851 None
9857 None
9859 8275 1583
9871 6363 3507
9883 9037 845
9887 None
9901 6567 3333
9907 2190 7716
9923 None
9929 None
9931 8520 1410
9941 None
9949 4527 5421
9967 9814 152
9973 6125 3847