API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 25th, 2019
109
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 24.63 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <time.h>
  5. #include <algorithm>
  6. #include <cmath>
  7.  
  8. using namespace std;
  9.  
  10. bool chet = true;
  11. bool NEG = false;
  12. vector <vector <int>> vec_bin_gen;
  13. vector <vector <int>> vec_gen;
  14. vector <vector <int>> vec_gen_1;
  15. vector <int> mod = {9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9, 9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9};
  16.  
  17. vector <int> multy (vector <int> U, vector <int> V)
  18. {
  19. vector <int> W(U.size() + V.size() + 1);
  20. if (V.size() > U.size() || (V.size() == U.size() && V > U))
  21. swap(U, V);
  22.  
  23. int m = int(V.size());
  24. U.push_back(0);
  25.  
  26. int t;
  27. int k = 0;
  28. for (int j = 0; j < m; j++)
  29. {
  30. for (int i = 0; i < U.size(); i++)
  31. {
  32. t = U[i] * V[j] + W[i + j] + k;
  33. W[i + j] = t % 10;
  34. k = t / 10;
  35. }
  36. }
  37.  
  38. if (W.size() > 1)
  39. {
  40. int n = int(W.size() - 1);
  41. while (W[n] == 0 && W.size() > 1)
  42. {
  43. W.pop_back();
  44. n--;
  45. }
  46. }
  47. return W;
  48. }
  49.  
  50. vector <int> difference (vector <int> U, vector <int> V)
  51. {
  52. int m = int(max(U.size(), V.size()));
  53. if (U.size() > 1)
  54. {
  55. int n = int(U.size() - 1);
  56. while (U[n] == 0 && U.size() > 1)
  57. {
  58. U.pop_back();
  59. n--;
  60. }
  61. }
  62.  
  63. if (V.size() > 1)
  64. {
  65. int n = int(V.size() - 1);
  66. while (V[n] == 0 && V.size() > 1)
  67. {
  68. V.pop_back();
  69. n--;
  70. }
  71. }
  72.  
  73. reverse(U.begin(), U.end());
  74. reverse(V.begin(), V.end());
  75. if (V.size() > U.size() || (V.size() == U.size() && V > U))
  76. {
  77. swap(U, V);
  78. NEG = true;
  79. }
  80. reverse(U.begin(), U.end());
  81. reverse(V.begin(), V.end());
  82. if (V.size() < U.size())
  83. {
  84. int r = int(U.size() - V.size());
  85. for (int i = r; i > 0; i--)
  86. V.push_back(0);
  87. }
  88.  
  89. vector <int> W;
  90. int k = 0;
  91. for (int j = 0; j < U.size(); j++)
  92. {
  93. W.push_back((U[j] - V[j] + k + 10) % 10);
  94. k = (U[j] - V[j] + k - 9) / 10;
  95. }
  96.  
  97. for (int i = 0; i < m; i++)
  98. W.push_back(0);
  99. NEG = false;
  100.  
  101. if (W.size() > 1)
  102. {
  103. int n = int(W.size() - 1);
  104. while (W[n] == 0 && W.size() > 1)
  105. {
  106. W.pop_back();
  107. n--;
  108. }
  109. }
  110. return W;
  111. }
  112.  
  113. vector <int> difference_1 (vector <int> U, vector <int> V)
  114. {
  115. int m = int(max(U.size(), V.size()));
  116. if (U.size() > 1)
  117. {
  118. int n = int(U.size() - 1);
  119. while (U[n] == 0 && U.size() > 1)
  120. {
  121. U.pop_back();
  122. n--;
  123. }
  124. }
  125.  
  126. if (V.size() > 1)
  127. {
  128. int n = int(V.size() - 1);
  129. while (V[n] == 0 && V.size() > 1)
  130. {
  131. V.pop_back();
  132. n--;
  133. }
  134. }
  135.  
  136. reverse(U.begin(), U.end());
  137. reverse(V.begin(), V.end());
  138. if (V.size() > U.size() || (V.size() == U.size() && V > U))
  139. {
  140. swap(U, V);
  141. NEG = true;
  142. }
  143. reverse(U.begin(), U.end());
  144. reverse(V.begin(), V.end());
  145. if (V.size() < U.size())
  146. {
  147. int r = int(U.size() - V.size());
  148. for (int i = r; i > 0; i--)
  149. V.push_back(0);
  150. }
  151.  
  152. vector <int> W;
  153. int k = 0;
  154. for (int j = 0; j < U.size(); j++)
  155. {
  156. W.push_back((U[j] - V[j] + k + 10) % 10);
  157. k = (U[j] - V[j] + k - 9) / 10;
  158. }
  159.  
  160. for (int i = 0; i < m; i++)
  161. W.push_back(0);
  162.  
  163. return W;
  164. }
  165.  
  166.  
  167. vector <int> addition (vector <int> U, vector <int> V)
  168. {
  169. int m = int(max(U.size(), V.size()));
  170. if (U.size() > 1)
  171. {
  172. int n = int(U.size() - 1);
  173. while (U[n] == 0 && U.size() > 1)
  174. {
  175. U.pop_back();
  176. n--;
  177. }
  178. }
  179.  
  180. if (V.size() > 1)
  181. {
  182. int n = int(V.size() - 1);
  183. while (V[n] == 0 && V.size() > 1)
  184. {
  185. V.pop_back();
  186. n--;
  187. }
  188. }
  189.  
  190. if (V.size() > U.size())
  191. swap(U, V);
  192.  
  193. vector <int> W;
  194. int k = 0;
  195. int r = int(U.size() - V.size());
  196. for (int i = r; i > 0; i--)
  197. V.push_back(0);
  198.  
  199. for (int j = 0; j < U.size(); j++)
  200. {
  201. W.push_back((U[j] + V[j] + k) % 10);
  202. k = (U[j] + V[j] + k) / 10;
  203. }
  204.  
  205. for (int i = 0; i < m; i++)
  206. W.push_back(0);
  207. return W;
  208. }
  209.  
  210. vector <int> addition_1 (vector <int> U, vector <int> V)
  211. {
  212. if (U.size() > 1)
  213. {
  214. int n = int(U.size() - 1);
  215. while (U[n] == 0 && U.size() > 1)
  216. {
  217. U.pop_back();
  218. n--;
  219. }
  220. }
  221.  
  222. if (V.size() > 1)
  223. {
  224. int n = int(V.size() - 1);
  225. while (V[n] == 0 && V.size() > 1)
  226. {
  227. V.pop_back();
  228. n--;
  229. }
  230. }
  231.  
  232. if (V.size() > U.size())
  233. swap(U, V);
  234.  
  235. vector <int> W;
  236. int k = 0;
  237. int r = int(U.size() - V.size());
  238. for (int i = r; i > 0; i--)
  239. V.push_back(0);
  240.  
  241. for (int j = 0; j < U.size(); j++)
  242. {
  243. W.push_back((U[j] + V[j] + k) % 10);
  244. k = (U[j] + V[j] + k) / 10;
  245. }
  246.  
  247. if (k == 1)
  248. W.push_back(k);
  249.  
  250. return W;
  251. }
  252.  
  253. vector <int> division (vector <int> U, vector <int> V)
  254. {
  255. bool fl = false;
  256.  
  257. if (U[0] % 2 == 1)
  258. chet = false;
  259.  
  260. if (U.size() < V.size() || (V.size() == U.size() && V[0] > U[0]))
  261. {
  262. vector <int> W;
  263. W.push_back(0);
  264. fl = true;
  265. return W;
  266. }
  267.  
  268. vector <int> W(U.size() + 1);
  269. if (!fl)
  270. {
  271. int cur, ost = 0;
  272. for (int j = int(U.size() - 1); j >= 0; j--)
  273. {
  274. cur = 10 * ost + U[j];
  275. W[j] = cur / V[0];
  276. ost = cur % V[0];
  277. }
  278.  
  279. if (W.size() > 1)
  280. {
  281. int n = int(W.size() - 1);
  282. while (W[n] == 0 && W.size() > 1)
  283. {
  284. W.pop_back();
  285. n--;
  286. }
  287. }
  288. }
  289. return W;
  290. }
  291.  
  292. vector <int> division_1 (vector <int> U, vector <int> V)
  293. {
  294. bool fl = false;
  295. if (U.size() < V.size() || (V.size() == U.size() && V[0] > U[0]))
  296. {
  297. vector<int> W;
  298. W.push_back(0);
  299. fl = true;
  300. return W;
  301. }
  302.  
  303. vector <int> W(U.size() + 1);
  304. if (!fl)
  305. {
  306. int cur, ost = 0;
  307. for (int j = int(U.size() - 1); j >= 0; j--)
  308. {
  309. cur = 10 * ost + U[j];
  310. W[j] = cur / V[0];
  311. ost = cur % V[0];
  312. }
  313.  
  314. if (W.size() > 1)
  315. {
  316. int n = int(W.size() - 1);
  317. while (W[n] == 0 && W.size() > 1)
  318. {
  319. W.pop_back();
  320. n--;
  321. }
  322. }
  323. }
  324. return W;
  325. }
  326.  
  327. vector <int> division_mod (vector <int> U, vector <int> V)
  328. {
  329. vector <int> vec_mod, W2_2;
  330. bool fl1 = false;
  331. if (U[0] == '0' && U.size() == 1)
  332. {
  333. fl1 = true;
  334. vec_mod.push_back(0);
  335. return vec_mod;
  336. }
  337.  
  338. bool fl = false;
  339. reverse(V.begin(), V.end());
  340. reverse(U.begin(), U.end());
  341. if (U.size() < V.size() || (V.size() == U.size() && V > U))
  342. {
  343. fl = true;
  344. reverse(U.begin(), U.end());
  345. return U;
  346. }
  347. reverse(V.begin(), V.end());
  348. reverse(U.begin(), U.end());
  349.  
  350. vector <int> W(U.size() + 1);
  351. if (!fl1 && !fl)
  352. {
  353. int cur, ost = 0;
  354. vector <int> Chastnoe(U.size());
  355. if (V.size() == 1)
  356. {
  357. for (int j = int(U.size() - 1); j >= 0; j--)
  358. {
  359. cur = 10 * ost + U[j];
  360. W[j] = cur / V[0];
  361. ost = cur % V[0];
  362. }
  363.  
  364. vec_mod.push_back(ost);
  365. return vec_mod;
  366. }
  367.  
  368. else
  369. {
  370. int ms = int(U.size() - V.size());
  371. int d = 10 / (V[V.size() - 1] + 1);
  372. vector <int> D;
  373. D.push_back(d);
  374. U = multy(U, D);
  375. V = multy(V, D);
  376. if (ms + V.size() > U.size() - 1)
  377. U.push_back(0);
  378. for (int j = ms; j >= 0; j--)
  379. {
  380. int qk = (U[j + V.size()] * 10 + U[j + V.size() - 1]) / V[V.size() - 1];
  381. int rk = (U[j + V.size()] * 10 + U[j + V.size() - 1]) % V[V.size() - 1];
  382. step1: if (qk == 10 || qk*V[V.size() - 2] > 10 * rk + U[j + V.size() - 2])
  383. {
  384. qk--;
  385. rk += V[V.size() - 1];
  386. if (rk < 10)
  387. goto step1;
  388. }
  389. vector <int> QK;
  390. QK.push_back(qk);
  391. int s = int(j + V.size());
  392. vector <int> chu(V.size() + 1);
  393. vector <int> raz(V.size() + 1);
  394. for (int f = s; f >= j; f--)
  395. chu[f - j] = U[f];
  396.  
  397. vector <int> chupa;
  398. for (int e = 0; e <= V.size(); e++)
  399. chupa.push_back(0);
  400. chupa.push_back(1);
  401.  
  402. raz = difference_1(chu, multy(QK, V));
  403. if (NEG)
  404. raz = difference_1(chupa, raz);
  405.  
  406. Chastnoe[j] = qk;
  407. if (NEG)
  408. {
  409. Chastnoe[j]--;
  410. raz = addition(V, raz);
  411. NEG = false;
  412. }
  413.  
  414. for (int f = s; f >= j; f--)
  415. U[f] = raz[f - j];
  416. }
  417.  
  418. if (Chastnoe.size() > 1)
  419. {
  420. int n = int(Chastnoe.size() - 1);
  421. while (Chastnoe[n] == 0 && Chastnoe.size() > 1)
  422. {
  423. Chastnoe.pop_back();
  424. n--;
  425. }
  426. }
  427.  
  428. vector <int> U2;
  429. for (int g = int(V.size() - 1); g >= 0; g--)
  430. U2.push_back(U[g]);
  431. reverse(U2.begin(), U2.end());
  432. vector <int> W2 (U2.size());
  433. for (int z = int(U2.size() - 1); z >= 0; z--)
  434. {
  435. cur = 10 * ost + U2[z];
  436. W2[z] = cur / D[0];
  437. ost = cur % D[0];
  438. }
  439. if (W2.size() > 1)
  440. {
  441. int n = int(W2.size() - 1);
  442. while (W2[n] == 0 && W2.size() > 1)
  443. {
  444. W2.pop_back();
  445. n--;
  446. }
  447. }
  448. NEG = false;
  449. W2_2 = W2;
  450. }
  451. }
  452. return W2_2;
  453. }
  454.  
  455. vector <int> division_chast (vector <int> U, vector <int> V)
  456. {
  457. vector <int> vec_mod, Chastnoe_2;
  458. bool fl1 = false;
  459. if (U[0] == '0' && U.size() == 1)
  460. {
  461. fl1 = true;
  462. vec_mod.push_back(0);
  463. return vec_mod;
  464. }
  465.  
  466. bool fl = false;
  467. reverse(V.begin(), V.end());
  468. reverse(U.begin(), U.end());
  469. if (U.size() < V.size() || (V.size() == U.size() && V > U))
  470. {
  471. fl = true;
  472. vec_mod.push_back(0);
  473. return vec_mod;
  474. }
  475. reverse(V.begin(), V.end());
  476. reverse(U.begin(), U.end());
  477.  
  478. vector <int> W(U.size() + 1);
  479. if (!fl1 && !fl)
  480. {
  481. int cur, ost = 0;
  482. vector <int> Chastnoe(U.size());
  483. if (V.size() == 1)
  484. {
  485. for (int j = int(U.size() - 1); j >= 0; j--)
  486. {
  487. cur = 10 * ost + U[j];
  488. W[j] = cur / V[0];
  489. ost = cur % V[0];
  490. }
  491.  
  492. if (W.size() > 1)
  493. {
  494. int n = int(W.size() - 1);
  495. while (W[n] == 0 && W.size() > 1)
  496. {
  497. W.pop_back();
  498. n--;
  499. }
  500. }
  501. return W;
  502. }
  503.  
  504. else
  505. {
  506. int ms = int(U.size() - V.size());
  507. int d = 10 / (V[V.size() - 1] + 1);
  508. vector <int> D;
  509. D.push_back(d);
  510. U = multy(U, D);
  511. V = multy(V, D);
  512. if (ms + V.size() > U.size() - 1)
  513. U.push_back(0);
  514. for (int j = ms; j >= 0; j--)
  515. {
  516. int qk = (U[j + V.size()] * 10 + U[j + V.size() - 1]) / V[V.size() - 1];
  517. int rk = (U[j + V.size()] * 10 + U[j + V.size() - 1]) % V[V.size() - 1];
  518. step1: if (qk == 10 || qk*V[V.size() - 2] > 10 * rk + U[j + V.size() - 2])
  519. {
  520. qk--;
  521. rk += V[V.size() - 1];
  522. if (rk < 10)
  523. goto step1;
  524. }
  525. vector <int> QK;
  526. QK.push_back(qk);
  527. int s = int(j + V.size());
  528. vector <int> chu(V.size() + 1);
  529. vector <int> raz(V.size() + 1);
  530. for (int f = s; f >= j; f--)
  531. chu[f - j] = U[f];
  532.  
  533. vector <int> chupa;
  534. for (int e = 0; e <= V.size(); e++)
  535. chupa.push_back(0);
  536. chupa.push_back(1);
  537.  
  538. raz = difference_1(chu, multy(QK, V));
  539. if (NEG)
  540. raz = difference_1(chupa, raz);
  541.  
  542. Chastnoe[j] = qk;
  543. if (NEG)
  544. {
  545. Chastnoe[j]--;
  546. raz = addition(V, raz);
  547. NEG = false;
  548. }
  549.  
  550. for (int f = s; f >= j; f--)
  551. U[f] = raz[f - j];
  552. }
  553.  
  554. if (Chastnoe.size() > 1)
  555. {
  556. int n = int(Chastnoe.size() - 1);
  557. while (Chastnoe[n] == 0 && Chastnoe.size() > 1)
  558. {
  559. Chastnoe.pop_back();
  560. n--;
  561. }
  562. }
  563. NEG = false;
  564. Chastnoe_2 = Chastnoe;
  565. }
  566. }
  567. return Chastnoe_2;
  568. }
  569.  
  570. vector <int> stepen_mod (vector <int> U, vector <int> V, vector <int> mod1)
  571. {
  572. vector <int> Y;
  573. Y.push_back(1);
  574. vector <int> N = V;
  575. vector <int> Z = U;
  576.  
  577. vector <int> del;
  578. del.push_back(2);
  579. while (!(N.size() == 1 && N[0] == 0))
  580. {
  581. N = division(N, del);
  582. if (chet)
  583. {
  584. Z = multy(Z, Z);
  585. Z = division_mod(Z, mod1);
  586. }
  587. else
  588. {
  589. Y = multy(Y, Z);
  590. Y = division_mod(Y, mod1);
  591.  
  592. if (N.size() == 1 && N[0] == 0)
  593. break;
  594. Z = multy(Z, Z);
  595. Z = division_mod(Z, mod1);
  596.  
  597. chet = true;
  598. }
  599. }
  600.  
  601. Y = division_mod(Y, mod1);
  602. if (Y.size() > 1)
  603. {
  604. int n = int(Y.size() - 1);
  605. while (Y[n] == 0 && Y.size() > 1)
  606. {
  607. Y.pop_back();
  608. n--;
  609. }
  610. }
  611. chet = true;
  612. return Y;
  613. }
  614.  
  615. vector <int> generator (int k)
  616. {
  617. srand(time(NULL));
  618. vector <int> rnd;
  619. step1:
  620. for (int i = 0; i < k ; i++)
  621. {
  622. int r = rand() % 10;
  623. rnd.push_back(r);
  624. }
  625.  
  626. reverse(rnd.begin(), rnd.end());
  627. if (rnd.size() > 1)
  628. {
  629. int n = int(rnd.size() - 1);
  630. while (rnd[n] == 0 && rnd.size() > 1)
  631. {
  632. rnd.pop_back();
  633. n--;
  634. }
  635. }
  636. reverse(rnd.begin(), rnd.end());
  637.  
  638. for (int i = 0; i < vec_gen.size(); i++)
  639. if (rnd == vec_gen[i])
  640. {
  641. rnd.clear();
  642. goto step1;
  643. }
  644.  
  645. vec_gen.push_back(rnd);
  646. return rnd;
  647. }
  648.  
  649. vector <int> generator_1 (int k)
  650. {
  651. vector <int> rnd;
  652. step2:
  653. for (int i = 0; i < k; i++)
  654. {
  655. int r = rand() % 10;
  656. rnd.push_back(r);
  657. }
  658.  
  659. reverse(rnd.begin(), rnd.end());
  660. if (rnd.size() > 1)
  661. {
  662. int n = int(rnd.size() - 1);
  663. while (rnd[n] == 0 && rnd.size() > 1)
  664. {
  665. rnd.pop_back();
  666. n--;
  667. }
  668. }
  669. reverse(rnd.begin(), rnd.end());
  670.  
  671. for (int i = 0; i < vec_gen_1.size(); i++)
  672. if (rnd == vec_gen_1[i])
  673. {
  674. rnd.clear();
  675. goto step2;
  676. }
  677.  
  678. vec_gen_1.push_back(rnd);
  679. return rnd;
  680. }
  681.  
  682. vector <int> generator_2 (int &k)
  683. {
  684. vector <int> rnd;
  685. if (k == 1)
  686. {
  687. rnd.push_back(1);
  688. return rnd;
  689. }
  690.  
  691. step1:
  692. rnd.push_back(1);
  693. for (int i = 0; i < k - 2; i++)
  694. {
  695. int r = rand() % 2;
  696. rnd.push_back(r);
  697. }
  698. rnd.push_back(1);
  699. for (int i = 0; i < vec_bin_gen.size(); i++)
  700. if (rnd == vec_bin_gen[i])
  701. {
  702. rnd.clear();
  703. goto step1;
  704. }
  705.  
  706. vec_bin_gen.push_back(rnd);
  707. return rnd;
  708. }
  709.  
  710. vector <int> to10 (vector <int> c)
  711. {
  712. int size = int(c.size());
  713. vector <int> to10_c(log2(size) + 1), vec_2, stepen;
  714. vec_2.push_back(2);
  715.  
  716. for (int i = 0; i < size; i++)
  717. {
  718. int st = size - i - 1;
  719. string ST;
  720. ST = to_string(st);
  721. for (int j = int(ST.size() - 1); j >= 0; j--)
  722. {
  723. string step_str;
  724. step_str = ST.substr(j, 1);
  725. int step_ch = atoi(step_str.c_str());
  726. stepen.push_back(step_ch);
  727. }
  728. vector <int> vec;
  729. vec.push_back(c[i]);
  730. to10_c = addition_1(to10_c, multy(vec, stepen_mod(vec_2, stepen, mod)));
  731. vec.clear();
  732. stepen.clear();
  733. }
  734.  
  735. if (to10_c.size() > 1)
  736. {
  737. int n = int(to10_c.size() - 1);
  738. while (to10_c[n] == 0 && to10_c.size() > 1)
  739. {
  740. to10_c.pop_back();
  741. n--;
  742. }
  743. }
  744. return to10_c;
  745. }
  746.  
  747. bool compare_for_v (vector <int> &V, vector <int> &U)
  748. {
  749. if (V.size() < U.size())
  750. return true;
  751. if (V.size() > U.size())
  752. return false;
  753. if (V == U)
  754. return false;
  755.  
  756. for (int g = 0; g < V.size(); g++)
  757. {
  758. if (V[g] > U[g])
  759. return false;
  760. else
  761. if (V[g] < U[g])
  762. return true;
  763. }
  764. return true;
  765. }
  766.  
  767. bool isprime (vector <int> c)
  768. {
  769. if (c.size() == 1 && (c[0] == 0 || c[0] == 1 || c[0] == 2))
  770. return true;
  771.  
  772. vector <int> q, a, vec_1, vec_2;
  773. a.push_back(0);
  774. vec_1.push_back(1);
  775. vec_2.push_back(2);
  776.  
  777. int count = 0;
  778. if (c != vec_1)
  779. {
  780. q = difference(c, vec_1);
  781.  
  782. do { q = division_chast(q, vec_2); count++; } while (q[0] % 2 == 0);
  783.  
  784. vector <int> vec_i, vec_i_max, vec_count;
  785. vec_i.push_back(1);
  786. vec_i_max = difference(c, vec_1);
  787. vec_count.push_back(4);
  788. vec_count.push_back(0);
  789.  
  790. if (compare_for_v(vec_count, vec_i_max))
  791. vec_i_max = vec_count;
  792.  
  793. for (vec_i; compare_for_v(vec_i, vec_i_max); vec_i = addition_1(vec_i, vec_1))
  794. {
  795. vector <int> diff = difference(c, vec_1);
  796. reverse(diff.begin(), diff.end());
  797. while (compare_for_v(a, vec_1) || compare_for_v(diff, a))
  798. a = generator_1(int(difference(c, vec_1).size()));
  799.  
  800. reverse(a.begin(), a.end());
  801. if (stepen_mod(a, difference(c, vec_1), c) != vec_1)
  802. return false;
  803.  
  804. a = stepen_mod(a, q, c);
  805. if (a != vec_1)
  806. {
  807. for (int e = 0; e < count; e++)
  808. if (a != vec_1 && a != difference(c, vec_1))
  809. a = division_mod(multy(a, a), c);
  810. if (a == vec_1)
  811. return false;
  812. }
  813. a.clear();
  814. }
  815. return true;
  816. }
  817. else
  818. return false;
  819. }
  820.  
  821. int main ()
  822. {
  823. setlocale(LC_ALL, "Russian");
  824. string bit;
  825. cout << "Введите битность числа р = ";
  826. cin >> bit;
  827.  
  828. vector <int> bit_p, p_control;
  829. for (int i = int(bit.size() - 1); i >= 0; i--)
  830. bit_p.push_back(atoi(bit.substr(i, 1).c_str()));
  831.  
  832. int bit1 = atoi(bit.c_str());
  833. if (bit1 <= 3)
  834. {
  835. cout << "Ошибка" << endl;
  836. return 0;
  837. }
  838. bit1 = bit1 / 2;
  839.  
  840. vector <int> vec_1, vec_2, q;
  841. vec_1.push_back(1);
  842. vec_2.push_back(2);
  843.  
  844. step3:
  845. q = generator_2(bit1);
  846. q = to10(q);
  847. if (!isprime(q))
  848. {
  849. vec_gen_1.clear();
  850. goto step3;
  851. }
  852.  
  853. vector <int> down_gr_p, up_gr_p, down_gr_s, up_gr_s, gr1 = down_gr_s, gr2 = up_gr_s, p;
  854. down_gr_p = stepen_mod(vec_2, difference(bit_p, vec_1), mod);
  855. up_gr_p = stepen_mod(vec_2, bit_p, mod);
  856. down_gr_s = division_chast(difference(down_gr_p, vec_1), q);
  857. up_gr_s = addition_1(division_chast(difference(up_gr_p, vec_1), q), vec_1);
  858. reverse(down_gr_p.begin(), down_gr_p.end());
  859. reverse(up_gr_p.begin(), up_gr_p.end());
  860. reverse(gr1.begin(), gr1.end());
  861. reverse(gr2.begin(), gr2.end());
  862.  
  863. vector <int> s, predel;
  864. s.push_back(1);
  865. vector <vector <int>> ss;
  866. predel.push_back(int(ss.size()));
  867.  
  868. step4:
  869. s = generator(int(up_gr_s.size()));
  870. if ((!compare_for_v(s, gr1) && !compare_for_v(gr2, s)) && s[s.size() - 1] % 2 == 0)
  871. {
  872. vector <int> S = s;
  873. reverse(S.begin(), S.end());
  874.  
  875. p = addition_1(multy(q, S), vec_1);
  876.  
  877. vector <int> V1, V2, V3;
  878. V1 = stepen_mod(addition_1(multy(vec_2, q), vec_1), vec_2, mod);
  879. V2 = stepen_mod(vec_2, multy(q, S), p);
  880. V3 = stepen_mod(vec_2, S, p);
  881. reverse(V1.begin(), V1.end());
  882. reverse(V2.begin(), V2.end());
  883. reverse(V3.begin(), V3.end());
  884. reverse(p.begin(), p.end());
  885.  
  886. if (compare_for_v(p, V1) && (V2 == vec_1) && (V3 != vec_1) && compare_for_v(p, up_gr_p) && compare_for_v(down_gr_p, p))
  887. p_control = p;
  888.  
  889. else
  890. {
  891. vector <int> vec = difference(difference(up_gr_s, down_gr_s), division_1(difference(up_gr_s, down_gr_s), vec_2));
  892. bool fl = false;
  893. if (predel.size() < vec.size())
  894. fl = true;
  895. if (predel.size() > vec.size())
  896. fl = false;
  897. if (predel == vec)
  898. fl = false;
  899.  
  900. for (int g = 0; g < predel.size(); g++)
  901. if (predel[g] > vec[g])
  902. fl = false;
  903. else
  904. if (predel[g] < vec[g])
  905. fl = true;
  906. if (fl)
  907. ss.push_back(S);
  908. predel = addition_1(predel, vec_1);
  909. goto step4;
  910. }
  911. }
  912. else
  913. goto step4;
  914.  
  915. vector <int> vec = difference(difference(up_gr_s, down_gr_s), division_1(difference(up_gr_s, down_gr_s), vec_2));
  916. bool fl = false;
  917. if (predel.size() < vec.size())
  918. fl = true;
  919. if (predel.size() > vec.size())
  920. fl = false;
  921. if (predel == vec)
  922. fl = false;
  923.  
  924. for (int g = 0; g < predel.size(); g++)
  925. if (predel[g] > vec[g])
  926. fl = false;
  927. else
  928. if (predel[g] < vec[g])
  929. fl = true;
  930. if (!fl)
  931. {
  932. vec_bin_gen.clear();
  933. vec_gen.clear();
  934. vec_gen_1.clear();
  935. goto step3;
  936. }
  937.  
  938. vector <int> g;
  939. g.push_back(1);
  940.  
  941. cout << "p = ";
  942. for (int i = 0; i < p_control.size(); i++)
  943. cout << p_control[i];
  944. cout << endl;
  945. cout << "q = ";
  946. for (int i = 0; i < q.size(); i++)
  947. cout << q[i];
  948. cout << endl;
  949.  
  950. reverse (p_control.begin(), p_control.end());
  951. while (g == vec_1)
  952. {
  953. vector <int> a, p_2;
  954. p_2 = difference(p_control, vec_2);
  955. reverse(p_2.begin(), p_2.end());
  956.  
  957. while (compare_for_v(a, vec_2) || compare_for_v(p_2, a))
  958. a = generator_1(int(p_control.size()));
  959.  
  960. vector <int> p_1, p_q;
  961. p_1 = difference(p_control, vec_1);
  962. p_q = division_chast(p_1, q);
  963. g = stepen_mod(a, p_q, p_control);
  964. }
  965.  
  966. reverse(g.begin(), g.end());
  967. cout << "g = ";
  968. for (int i = 0; i < g.size(); i++)
  969. cout << g[i];
  970. cout << endl;
  971. return 0;
  972. }
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!