Про алгоритм Ферма

День добрый.



Ниже вы видете код, который по моему замыслу должен находить простой

делитель от введенного числа n по алгоритму Ферма.

О том как работает алгоритм можно почитать в "Введение в теорию чисел

Алгоритм RSA", главы 2-8 сего труда на www.cryptography.ru



Вот сам код:

Код (Text):

1.  
2.  
3. #include <iostream>
4.  
5. #include <math.h>
6.  
7.  
8.  
9. using namespace std;
10.  
11.  
12.  
13. int main()
14.  
15. {
16.  
17.     int n = 0;
18.  
19.     int x = 0;
20.  
21.     double y = 0;
22.  
23.  
24.  
25.     cout << "\nEnter number: ";
26.  
27.     cin >> n;
28.  
29.  
30.  
31.     if(!(n % 2)) // все числа с делимостью на 2, разложимы
32.  
33.     {
34.  
35.         cout << "\nPrime devisor: 2\n";
36.  
37.         return 0;
38.  
39.     }
40.  
41.  
42.  
43. // Step 1.
44.  
45.     x = (int)sqrt(n);
46.  
47.     if(n == (x*x))  // для случаев подобных: - 3^2=9
48.  
49.     {
50.  
51.     cout << "\nPrime devisor: " << x << "\n";
52.  
53.     }
54.  
55.  
56.  
57. // Step 2.
58.  
59.         else
60.  
61.         {
62.  
63.         x++;
64.  
65.         while(true)
66.  
67.         {
68.  
69.             if(x == (n+1)/2)
70.  
71.             {
72.  
73.             cout << "\nPrime devisor: " << x << "\n";
74.  
75.             break;
76.  
77.             }
78.  
79.                 else
80.  
81.                 {
82.  
83.             //Step 3.
84.  
85.                 y = sqrt((x*x)-n);
86.  
87.                     if(!(y-(int)y)) // дробно ли число y?
88.  
89.                     {
90.  
91.                     cout << "\nPrime devisor: " << y << "\n";
92.  
93.                     break;
94.  
95.                     }
96.  
97.                 x++;
98.  
99.                 }
100.  
101.         }
102.  
103.     }
104.  
105.     return 0;
106.  
107. }
108.  
109. [\code]
110.  
111.  
112.  
113. я испытываю сложность в отладке шагов 2 и 3.
114.  
115.  
116.  
117. Просьба:
118.  
119.  
120.  
121. Если не трудно ткуть носом: где я допускаю ошибки?
122.  
123.  
124.  
125. А ошибки есть, т.к. на простое число 19 программа находит "делитель" 10!

 

Текущий код:

_1892486113__AlgorithmFerma.cpp

 

Вроде убил баги

136630756__AlgorithmFerma.cpp

 

Если не трудно выложи исходный код прям в сообщение...
Мне не позволяют почему то скачать приложенные файлики

 

Я когда-то разбирался с этим методом, код рабочий:

Код (Text):

1. int sq_root (int n) {
2.     return (int) sqrt (n + .0);
3. }
4.  
5. template <class T, class T2>
6. T ferma (const T & n, T2 unused)
7. {
8.     T2
9.         x = sq_root (n),
10.         y = 0,
11.         r = x*x - y*y - n;
12.     for (;;)
13.         if (r == 0)
14.             return x!=y ? x-y : x+y;
15.         else
16.             if (r > 0)
17.             {
18.                 r -= y+y+1;
19.                 ++y;
20.             }
21.             else
22.             {
23.                 r += x+x+1;
24.                 ++x;
25.             }
26. }