API tools faq
paste
Advertisement
grhkm

rsa-lcg-2

grhkm
Dec 15th, 2024
19
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.37 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <chrono>
  3. #include <thread>
  4.  
  5. #include "flint/fmpz.h"
  6. #include "flint/fmpz_factor.h"
  7. #include "flint/fmpz_mod.h"
  8. #include "flint/fmpz_mod_poly.h"
  9. #include "flint/fmpz_mod_poly_factor.h"
  10.  
  11. int main() {
  12.   auto start_t = std::chrono::high_resolution_clock::now();
  13.  
  14.   fmpz_t c;
  15.   fmpz_init(c);
  16.  
  17.   fmpz_t NEG_n;
  18.   fmpz_init(NEG_n);
  19.   fmpz_t n;
  20.   fmpz_init(n);
  21.  
  22.   fmpz_t POW_2;
  23.   fmpz_init(POW_2);
  24.   fmpz_set_str(POW_2, "115792089237316195423570985008687907853269984665640564039457584007913129639936", 10);
  25.  
  26.   fmpz_factor_t FACTOR_POW_2;
  27.   fmpz_factor_init(FACTOR_POW_2);
  28.   fmpz_factor_trial(FACTOR_POW_2, POW_2, 5);
  29.  
  30.   fmpz_mod_ctx_t fctx;
  31.   fmpz_mod_ctx_init(fctx, POW_2);
  32.  
  33.   fmpz_mod_poly_t f;
  34.   fmpz_mod_poly_init(f, fctx);
  35.  
  36.   fmpz_t c1, c2, c3;
  37.   fmpz_init(c1);
  38.   fmpz_init(c2);
  39.   fmpz_init(c3);
  40.  
  41.   fmpz_mod_poly_factor_t fac;
  42.   fmpz_mod_poly_factor_init(fac, fctx);
  43.  
  44.   // seed
  45.   fmpz_t s;
  46.   fmpz_init(s);
  47.  
  48.   // LCG computations
  49.   fmpz_t tmp_s, seed_, seed__, p;
  50.   fmpz_init(tmp_s);
  51.   fmpz_init(seed_);
  52.   fmpz_init(seed__);
  53.   fmpz_init(p);
  54.  
  55.   const bool TEST = false;
  56.   if (TEST) {
  57.     fmpz_set_str(c, "2665094466720861055234275890206149281861672608341637838010768686997714133359", 10);
  58.     fmpz_set_str(NEG_n, "75332168850584959901450179103897629190438040981617500425343266796883448566543", 10);
  59.     fmpz_set_str(
  60.         n,
  61.         "353647571714999736072104341124233651057213714708122904095478713893663730479240157064601062897650458210097434355914183345289487500224919579787246530437698291448386975895645878510859951741892273473789376832458299170850654511827890650742439667469262292079621903414331289303262990543348537826168586893084656666639365398668042937310930241300947125293607516996378174061271609861706009834998660960746310857194103971415568823033216273952409246097935991158967396322492409845257613635102541420343856455273117905803133679299028997370937710655280339196930898550640285907237735222613222309441933270313866557915787734708826188169344041457185282000444780478621174270135326407805315529049804846216966427117104385937952974279806364471097245852872224811136040435472170916772342470378270588813990962599109861003795898230208201204127397300243952947417825482221500393640827813050410311877579176593552042943403534573002689069215752148429953951040588486638221708312774975369304688146593939770186918000813869836203172688167622244660598897840567413896048432967901665250552155403987746924573434732018828447909075483189331608192665316841486890959367260574465610825623614015714560909038952574085011646824604401272315196002098716845599996350838459792666015165681",
  62.         10);
  63.   } else {
  64.     fmpz_set_str(c, "14258939715516539295587731120991968901228171455016001595761489750577784177213", 10);
  65.     fmpz_set_str(NEG_n, "1844117613169056713561974712208487723025450897929645549714183364695302665843", 10);
  66.     fmpz_set_str(
  67.         n,
  68.         "279784521303926518544200383491171400996467006054806060652945044514173580730320793076951350168517896308345078513333979433742090849938580604359515861344088875721354836410510396140219655796215325682295239294661185563708496490830500773420871847769568879274978173218440545663363350310752698066412613793738234395676975963986090446949443295350235071286869321557833967521199446244573020803085515110891641843096725596572980675877230459500589604078432572911282759481893882548258867802789628543364574694501159808895930747113406016718685856976531978713324829507636743778130758650283045513372598798114943752532619142439604369129493324057181519512588183783756314385380800844831034863151900295735342816476791991454383732133474515109758087482912794282007801160780475284011802960270750792620686906175026995623082009841402872948756740311519047998978234628057595438481437871594714428834059691733188294695393205472914443179153321670750219104306769911019089432918102588905808629421158434486927928786793524017503900505368724824170796339023214910404096208544407500008089429770878575702088992309354303731919302687039737672125268143820658069899761163750521000478474705014645224845757836226858836333259628284972467671764606702417658922805838428375959908059533",
  69.         10);
  70.   }
  71.  
  72.   fmpz_t c4;
  73.   fmpz_init(c4);
  74.   fmpz_mul_ui(c4, c, 4);
  75.  
  76.   fmpz_t c42;
  77.   fmpz_init(c42);
  78.   fmpz_mul(c42, c4, c4);
  79.  
  80.   fmpz_t c43;
  81.   fmpz_init(c43);
  82.   fmpz_mul(c43, c42, c4);
  83.  
  84.   unsigned long long iter = 0;
  85.   unsigned long long primes = 0;
  86.   for (unsigned long long N = 653;; ++N) {
  87.     auto end_t = std::chrono::high_resolution_clock::now();
  88.     auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_t - start_t);
  89.     printf("\x1b[32m[%11.3Lfm | %11.3Lfm / 1e9]\x1b[0m N = %llu\n", ((long double) elapsed.count()) / 60000.0, ((long double) elapsed.count() * 1e9) / (60000.0 * iter), N);
  90.  
  91.     if (primes >= 4) {
  92.       printf("\x1b[35mProgram took %11.3Lf minutes.\x1b[0m\n", ((long double) elapsed.count()) / 60000.0);
  93.       return 0;
  94.     }
  95.  
  96.     // t1 = N
  97.     for (unsigned long long t1 = N; t1 <= N; ++t1) {
  98.       for (unsigned long long t2 = 1; t2 <= N; ++t2) {
  99.         for (unsigned long long t3 = 1; t3 <= N; ++t3) {
  100.           ++iter;
  101.           fmpz_mul_ui(c3, c4, 3 * t1 + 2 * t2 + t3);
  102.           fmpz_mul_ui(c2, c42, t1 * (2 * t1 + 2 * t2 + t3) + (t1 + t2) * (t1 + t2 + t3));
  103.           fmpz_mul_ui(c1, c43, t1 * (t1 + t2) * (t1 + t2 + t3));
  104.           fmpz_mod_poly_set_coeff_ui(f, 4, 1, fctx);
  105.           fmpz_mod_poly_set_coeff_fmpz(f, 3, c3, fctx);
  106.           fmpz_mod_poly_set_coeff_fmpz(f, 2, c2, fctx);
  107.           fmpz_mod_poly_set_coeff_fmpz(f, 1, c1, fctx);
  108.           fmpz_mod_poly_set_coeff_fmpz(f, 0, NEG_n, fctx);
  109.  
  110.           fmpz_mod_poly_roots_factored(fac, f, 1, FACTOR_POW_2, fctx);
  111.           for (size_t idx = 0; idx < fac->num; ++idx) {
  112.             // fmpz_mod_poly_print_pretty(fac->poly + idx, "x", fctx);
  113.             fmpz_mod_poly_get_coeff_fmpz(s, fac->poly + idx, 0, fctx);
  114.             fmpz_mod_neg(s, s, fctx);
  115.  
  116.             // test seed
  117.             fmpz_mod_set_fmpz(seed_, s, fctx);
  118.             for (unsigned long long t = 0; t <= t1 + t2 + t3; ++t) {
  119.               // mutable version of seed_
  120.               fmpz_mod_set_fmpz(seed__, seed_, fctx);
  121.  
  122.               // p = seed_
  123.               fmpz_set(p, seed__);
  124.               // p += ((seed_ - c) % 2^256) << 256
  125.               fmpz_mod_sub_fmpz(seed__, seed__, c, fctx);
  126.               fmpz_mul_2exp(tmp_s, seed__, 256);
  127.               fmpz_add(p, p, tmp_s);
  128.               // p += ((seed_ - c) % 2^256) << 512
  129.               fmpz_mod_sub_fmpz(seed__, seed__, c, fctx);
  130.               fmpz_mul_2exp(tmp_s, seed__, 512);
  131.               fmpz_add(p, p, tmp_s);
  132.               // p += ((seed_ - c) % 2^256) << 768
  133.               fmpz_mod_sub_fmpz(seed__, seed__, c, fctx);
  134.               fmpz_mul_2exp(tmp_s, seed__, 768);
  135.               fmpz_add(p, p, tmp_s);
  136.  
  137.               if ((t == 0) && !fmpz_divisible(n, p)) {
  138.                 break;
  139.               }
  140.  
  141.               // if (((t == 0) || (t == t1) || (t == t1 + t2) || (t == t1 + t2 + t3)) && fmpz_divisible(n, p)) {
  142.               if ((t == 0) || (t == t1) || (t == t1 + t2) || (t == t1 + t2 + t3)) {
  143.                 printf("\x1b[36m");
  144.                 fmpz_print(p);
  145.                 printf("\x1b[0m\n");
  146.                 ++primes;
  147.               }
  148.  
  149.               fmpz_add(seed_, seed_, c4);
  150.             }
  151.           }
  152.         }
  153.       }
  154.     }
  155.  
  156.     // t2 = N
  157.     for (unsigned long long t1 = 1; t1 <= N; ++t1) {
  158.       for (unsigned long long t2 = N; t2 <= N; ++t2) {
  159.         for (unsigned long long t3 = 1; t3 <= N; ++t3) {
  160.           ++iter;
  161.           fmpz_mul_ui(c3, c4, 3 * t1 + 2 * t2 + t3);
  162.           fmpz_mul_ui(c2, c42, t1 * (2 * t1 + 2 * t2 + t3) + (t1 + t2) * (t1 + t2 + t3));
  163.           fmpz_mul_ui(c1, c43, t1 * (t1 + t2) * (t1 + t2 + t3));
  164.           fmpz_mod_poly_set_coeff_ui(f, 4, 1, fctx);
  165.           fmpz_mod_poly_set_coeff_fmpz(f, 3, c3, fctx);
  166.           fmpz_mod_poly_set_coeff_fmpz(f, 2, c2, fctx);
  167.           fmpz_mod_poly_set_coeff_fmpz(f, 1, c1, fctx);
  168.           fmpz_mod_poly_set_coeff_fmpz(f, 0, NEG_n, fctx);
  169.  
  170.           fmpz_mod_poly_roots_factored(fac, f, 1, FACTOR_POW_2, fctx);
  171.           for (size_t idx = 0; idx < fac->num; ++idx) {
  172.             // fmpz_mod_poly_print_pretty(fac->poly + idx, "x", fctx);
  173.             fmpz_mod_poly_get_coeff_fmpz(s, fac->poly + idx, 0, fctx);
  174.             fmpz_mod_neg(s, s, fctx);
  175.  
  176.             // test seed
  177.             fmpz_mod_set_fmpz(seed_, s, fctx);
  178.             for (unsigned long long t = 0; t <= t1 + t2 + t3; ++t) {
  179.               // mutable version of seed_
  180.               fmpz_mod_set_fmpz(seed__, seed_, fctx);
  181.  
  182.               // p = seed_
  183.               fmpz_set(p, seed__);
  184.               // p += ((seed_ - c) % 2^256) << 256
  185.               fmpz_mod_sub_fmpz(seed__, seed__, c, fctx);
  186.               fmpz_mul_2exp(tmp_s, seed__, 256);
  187.               fmpz_add(p, p, tmp_s);
  188.               // p += ((seed_ - c) % 2^256) << 512
  189.               fmpz_mod_sub_fmpz(seed__, seed__, c, fctx);
  190.               fmpz_mul_2exp(tmp_s, seed__, 512);
  191.               fmpz_add(p, p, tmp_s);
  192.               // p += ((seed_ - c) % 2^256) << 768
  193.               fmpz_mod_sub_fmpz(seed__, seed__, c, fctx);
  194.               fmpz_mul_2exp(tmp_s, seed__, 768);
  195.               fmpz_add(p, p, tmp_s);
  196.  
  197.               if ((t == 0) && !fmpz_divisible(n, p)) {
  198.                 break;
  199.               }
  200.  
  201.               // if (((t == 0) || (t == t1) || (t == t1 + t2) || (t == t1 + t2 + t3)) && fmpz_divisible(n, p)) {
  202.               if ((t == 0) || (t == t1) || (t == t1 + t2) || (t == t1 + t2 + t3)) {
  203.                 printf("\x1b[36m");
  204.                 fmpz_print(p);
  205.                 printf("\x1b[0m\n");
  206.                 ++primes;
  207.               }
  208.  
  209.               fmpz_add(seed_, seed_, c4);
  210.             }
  211.           }
  212.         }
  213.       }
  214.     }
  215.  
  216.     // t3 = N
  217.     for (unsigned long long t1 = 1; t1 <= N; ++t1) {
  218.       for (unsigned long long t2 = 1; t2 <= N; ++t2) {
  219.         for (unsigned long long t3 = N; t3 <= N; ++t3) {
  220.           ++iter;
  221.           fmpz_mul_ui(c3, c4, 3 * t1 + 2 * t2 + t3);
  222.           fmpz_mul_ui(c2, c42, t1 * (2 * t1 + 2 * t2 + t3) + (t1 + t2) * (t1 + t2 + t3));
  223.           fmpz_mul_ui(c1, c43, t1 * (t1 + t2) * (t1 + t2 + t3));
  224.           fmpz_mod_poly_set_coeff_ui(f, 4, 1, fctx);
  225.           fmpz_mod_poly_set_coeff_fmpz(f, 3, c3, fctx);
  226.           fmpz_mod_poly_set_coeff_fmpz(f, 2, c2, fctx);
  227.           fmpz_mod_poly_set_coeff_fmpz(f, 1, c1, fctx);
  228.           fmpz_mod_poly_set_coeff_fmpz(f, 0, NEG_n, fctx);
  229.  
  230.           // if ((t1 == 79) && (t2 == 116) && (t3 == 131)) {
  231.           //   fmpz_mod_poly_print_pretty(f, "x", fctx);
  232.           //   printf("\n");
  233.           //   fmpz_mod_poly_factor_print_pretty(fac, "x", fctx);
  234.           //   printf("\n");
  235.           // }
  236.           fmpz_mod_poly_roots_factored(fac, f, 1, FACTOR_POW_2, fctx);
  237.           for (size_t idx = 0; idx < fac->num; ++idx) {
  238.             // fmpz_mod_poly_print_pretty(fac->poly + idx, "x", fctx);
  239.             fmpz_mod_poly_get_coeff_fmpz(s, fac->poly + idx, 0, fctx);
  240.             fmpz_mod_neg(s, s, fctx);
  241.  
  242.             // test seed
  243.             fmpz_mod_set_fmpz(seed_, s, fctx);
  244.             for (unsigned long long t = 0; t <= t1 + t2 + t3; ++t) {
  245.               // mutable version of seed_
  246.               fmpz_mod_set_fmpz(seed__, seed_, fctx);
  247.  
  248.               // p = seed_
  249.               fmpz_set(p, seed__);
  250.               // p += ((seed_ - c) % 2^256) << 256
  251.               fmpz_mod_sub_fmpz(seed__, seed__, c, fctx);
  252.               fmpz_mul_2exp(tmp_s, seed__, 256);
  253.               fmpz_add(p, p, tmp_s);
  254.               // p += ((seed_ - c) % 2^256) << 512
  255.               fmpz_mod_sub_fmpz(seed__, seed__, c, fctx);
  256.               fmpz_mul_2exp(tmp_s, seed__, 512);
  257.               fmpz_add(p, p, tmp_s);
  258.               // p += ((seed_ - c) % 2^256) << 768
  259.               fmpz_mod_sub_fmpz(seed__, seed__, c, fctx);
  260.               fmpz_mul_2exp(tmp_s, seed__, 768);
  261.               fmpz_add(p, p, tmp_s);
  262.  
  263.               if ((t == 0) && !fmpz_divisible(n, p)) {
  264.                 break;
  265.               }
  266.  
  267.               // if (((t == 0) || (t == t1) || (t == t1 + t2) || (t == t1 + t2 + t3)) && fmpz_divisible(n, p)) {
  268.               if ((t == 0) || (t == t1) || (t == t1 + t2) || (t == t1 + t2 + t3)) {
  269.                 printf("\x1b[36m");
  270.                 fmpz_print(p);
  271.                 printf("\x1b[0m\n");
  272.                 ++primes;
  273.               }
  274.  
  275.               fmpz_add(seed_, seed_, c4);
  276.             }
  277.           }
  278.         }
  279.       }
  280.     }
  281.   }
  282. }
  283.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!