2019
Paris, France

Prime number project

This is a personal project were I code the Rabin-Miller primality test in C to generate large prime numbers. The mathematical core of the algorithm is Fermat's little theorem, making the algorithm probabilistic. As of today, this algorithm has applications in cryptography were it is used to generate the two very large prime numbers needed for the RSA cryptosystem, the main asymetric crypto-algorithm used today for sensitive operations like bank transfer orders or online purchases.

n body image made by hand
The project is publicly available on github. Running the make command generates the executable, which is then called by the command "./premier". The following integer is found to be prime, using all primes below 61 as Miller's witnesses :

771 556 976 664 284 624 783 948 586 203 089 099 094 456 108 811 446 532 972 540 353 805 946 411 678 356 717 127 033 861 672 783 539 517 609 103 576 588 547 068 859 398 077 750 194 905 260 144 177 795 776 290 339 874 885 491 200 635 029 529 671 553 667 634 964 917 059 771 887 442 877 451 887 699 345 875 019 596 745 802 247 752 805 566 877 597 054 585 072 705 391 200 693 937 896 830 244 829 347 442 500 017 207 359 464 062 215 987 892 243 860 776 213 812 468 774 926 028 932 607 049 047 096 376 291 725 060 597 960 677 858 860 630 451 163 758 359 144 163 038 410 799 844 250 171 076 025 141 208 379 226 250 123 298 099 072 494 375 858 279 781 298 501 786 852 303 827 121 093 095 061 886 633 085 759 634 522 348 385 410 242 554 816 857 601 839 755 011 757 273 300 135 874 440 656 242 790 072 201 616 825 672 738 225 266 199 358 084 216 597 745 321 883 690 111 191 332 284 429 092 753 849 497 092 195 471 251 187 483 819 965 102 203 972 078 883 413 000 324 479 418 531 466 308 276 374 888 276 450 885 922 207 653 174 613 002 295 861 089 898 944 451 942 261 128 830 524 261 862 419 215 421 327 391 760 153 107 051 771 399 747 458 387 272 899 111 261 330 822 288 924 921 353 873 714 568 357 820 164 793 824 102 028 316 435 793 765 762 057 062 284 248 184 977 457 034 300 348 482 610 276 873 851 357 277 868 705 349 114 601 047 966 011 927 779 771 195 633 272 764 866 882 421 785 445 363 812 939 189 021 622 326 350 249 170 583 522 232 871 861 273 558 248 409 185 619 610 210 849 976 201 739 764 255 993 334 466 653 377 670 818 347 265 320 985 519 245 026 890 912 517 759 204 856 858 439 208 737 785 724 977 867 371 824 682 872 973 757 333 620 575 722 129 372 944 984 358 790 871 055 178 627 992 101 241 887 507 940 887 335 060 775 553 986 593 229 244 671 470 981 075 751 272 702 030 122 878 978 663 987 855 373 391 128 727 438 086 524 130 209 670 361 689 262 809 602 341 703 551 281 131 547 944 403
The work of Pomerance about the repartition of pseudoprime numbers in base 2 shows that the probability that this number is a pseudoprime number in base 2 is of the order of 10-367. Since all prime number below 61 were used, and not only 2, the probability that this number is composite is actually even smaller than that.

Some contents

Ainsi le petit prince, malgré la bonne volonté de son amour, avait vite douté d’elle. Il avait pris au sérieux des mots sans importance, et était devenu très malheureux.