Advertisement
TheDoskz

blabla

Apr 18th, 2021
948
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.29 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Numerics;
  4.  
  5. namespace Masha
  6. {
  7.     internal class Program
  8.     {
  9.         private static BigInteger GCD(BigInteger a, BigInteger b)
  10.         {
  11.             while (a != 0 && b != 0)
  12.             {
  13.                 if (a > b)
  14.                     a %= b;
  15.                 else
  16.                     b %= a;
  17.             }
  18.  
  19.             return a | b;
  20.         }
  21.  
  22.         private static BigInteger abs(BigInteger a)
  23.         {
  24.             if (a < 0)
  25.             {
  26.                 return a * -1;
  27.             }
  28.             return a;
  29.         }
  30.         public static void Main(string[] args)
  31.         {
  32.             BigInteger n = 3977;
  33.             BigInteger x = 2;
  34.             BigInteger y = 1;
  35.  
  36.             BigInteger step = 1;
  37.             for (int i = 1; i < n; i++)
  38.             {
  39.                 BigInteger x_prev = x;
  40.                 if (GCD(n, abs(x_prev-y)) != 1)
  41.                 {
  42.                     break;
  43.                 }
  44.                
  45.                 x = (x * x - 1) % n;
  46.                
  47.                 if (i == step)
  48.                 {
  49.                     step *= 2;
  50.                     y = x_prev;
  51.                 }
  52.                 Console.WriteLine(GCD(n,abs(x-y)));
  53.             }
  54.         }
  55.        
  56.     }
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement