Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Numerics;
- namespace Masha
- {
- internal class Program
- {
- private static BigInteger GCD(BigInteger a, BigInteger b)
- {
- while (a != 0 && b != 0)
- {
- if (a > b)
- a %= b;
- else
- b %= a;
- }
- return a | b;
- }
- private static BigInteger abs(BigInteger a)
- {
- if (a < 0)
- {
- return a * -1;
- }
- return a;
- }
- public static void Main(string[] args)
- {
- BigInteger n = 3977;
- BigInteger x = 2;
- BigInteger y = 1;
- BigInteger step = 1;
- for (int i = 1; i < n; i++)
- {
- BigInteger x_prev = x;
- if (GCD(n, abs(x_prev-y)) != 1)
- {
- break;
- }
- x = (x * x - 1) % n;
- if (i == step)
- {
- step *= 2;
- y = x_prev;
- }
- Console.WriteLine(GCD(n,abs(x-y)));
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement