rsacracker 0.9.1

use indicatif::ProgressBar;
use lazy_static::lazy_static;
use rug::{ops::Pow, Integer};
use std::str::FromStr;

use crate::{key::PrivateKey, Attack, Error, Parameters, Solution};

/// Product of all primes between 2 and x
fn p(x: usize) -> Integer {
    let mut h = Integer::from(1);

    for p in primal::Primes::all() {
        h *= p;
        if p == x {
            break;
        }
    }
    h
}

macro_rules! i {
    ($n:expr) => {
        Integer::from_str(stringify!($n)).unwrap()
    };
}

fn pow(x: u32, y: u32) -> Integer {
    Integer::from(x).pow(y)
}

lazy_static! {
    static ref CC_FIRST_KIND: Vec<(Integer, usize)> = vec![
        // Smallest known Cunningham chain of the first kind
        (1122659.into(), 7),    // 7 digits
        (19099919.into(), 8),   // 8 digits
        (85864769.into(), 9),   // 8 digits
        (26089808579u64.into(), 10),    // 11 digits
        (554688278429u64.into(), 12),   // 12 digits
        (665043081119u64.into(), 11),   // 12 digits
        (4090932431513069u64.into(), 13),   // 16 digits
        (95405042230542329u64.into(), 14),  // 17 digits
        (90616211958465842219u128.into(), 15),  // 20 digits
        (810433818265726529159u128.into(), 16), // 21 digits
        (2759832934171386593519u128.into(), 17),    // 22 digits
        // Record history
        (2618163402417u64 * pow(2, 1290000) - 1, 2),    // 388342 digits
        (18543637900515u64 * pow(2, 666667) - 1, 2),    // 200701 digits
        (183027 * pow(2, 265440) - 1, 2),   // 79911 digits
        (648621027630345u64 * pow(2, 253824) - 1, 2),   // 76424 digits
        (620366307356565u64 * pow(2, 253824) - 1, 2),   // 76424 digits
        (607095 * pow(2, 176311) - 1, 2),   // 53081 digits
        (48047305725u64 * pow(2, 172403) - 1, 2),   // 51910 digits
        (137211941292195u64 * pow(2, 171960) - 1, 2),   // 51780 digits
        (7068555 * pow(2, 121301) - 1, 2),  // 36523 digits
        (2540041185u64 * pow(2, 114729) - 1, 2),    // 34547 digits
        (18912879 * pow(2, 98395) - 1, 2),  // 29628 digits
        (1213822389 * pow(2, 81131) - 1, 2),    // 24432 digits
        (109433307 * pow(2, 66452) - 1, 2), // 20013 digits
        (3714089895285u64 * pow(2, 60000) - 1, 2),  // 18075 digits
        (18131 * p(22817) - 1, 2),  // 9853 digits
        (18458709 * pow(2, 32611) - 1, 2),  // 9825 digits
        (14516877 * pow(2, 24176) - 1, 2),  // 7285 digits
        (72021 * pow(2, 23630) - 1, 2), // 7119 digits
        (276311 * pow(2, 19003) + 1, 2),    // 5726 digits
        (92305 * pow(2, 16998) + 1, 2), // 5122 digits
        (8069496435u64 * pow(10, 5072) - 1, 2), // 5082 digits
        (470943129 * pow(2, 16352) - 1, 2), // 4932 digits
        (5415312903u64 * pow(10, 4526) - 1, 2), // 4536 digits
        (47013511545u64 * pow(10, 2999) - 1, 2),    // 3010 digits
        (2926924 * pow(10, 2032) + 1, 2),   // 2039 digits
        (713851138 * pow(10, 1854) + 1, 2), // 1863 digits
        (39051 * pow(2, 6001) - 1, 2),  // 1812 digits
        (1128330746865u64 * pow(2, 66439) - 1, 3),  // 20013 digits
        (1815615642825u64 * pow(2, 44044) - 1, 3),  // 13271 digits
        (742478255901u64 * pow(2, 40067) + 1, 3),   // 12074 digits
        (996824343 * pow(2, 40072) + 1, 3), // 12072 digits
        (333645655005u64 * pow(2, 35547) - 1, 3),   // 10713 digits
        (5110664609396115u64 * pow(2, 34944) - 1, 3),   // 10535 digits
        (3020255265u64 * pow(2, 20023) - 1, 3), // 6038 digits
        (2288999415u64 * pow(2, 15937) - 1, 3), // 4807 digits
        (1110159213 * pow(2, 15164) + 1, 3),    // 4574 digits
        (1838313165 * pow(2, 10219) - 1, 3),    // 3086 digits
        (1531785651 * pow(2, 10107) + 1, 3),    // 3052 digits
        (1999446945 * pow(2, 6626) - 1, 3), // 2004 digits
        (734257203 * pow(2, 5000) + 1, 3),  // 1515 digits
        (651358155 * pow(2, 3291) - 1, 3),  // 1000 digits
        (13720852541u64 * p(7877) - 1, 4),  // 3384 digits
        (28961560189u64 * p(7517) - 1, 4),  // 3217 digits
        (28904981097u64 * p(6703) - 1, 4),  // 2882 digits
        (1249097877 * p(6599) - 1, 4),  // 2835 digits
        (119184698 * p(5501) - 1, 4),   // 2354 digits
        (1707223185 * p(3049) - 1, 4),  // 1308 digits
        (433098705 * p(2633) - 1, 4),   // 1117 digits
        (742155874 * p(2381) - 1, 4),   // 1019 digits
        (35443364 * p(1013) - 1, 4),    // 429 digits
        (31017701152691334912u128 * p(4091) - 1, 5),    // 1765 digits
        (3387614923u64 * p(3917) - 1, 5),   // 1680 digits
        (199949435137u64 * p(3499) - 1, 5), // 1493 digits
        (361296035282u64 * p(3023) - 1, 5), // 1299 digits
        (4250172704u64 * p(2749) - 1, 5),   // 1183 digits
        (357487161295u64 * p(1693) - 1, 5), // 727 digits
        (148809453 * p(1069) - 1, 5),   // 460 digits
        (828114253 * p(991) - 1, 5),    // 422 digits
        (504856309 * p(953) - 1, 5),    // 407 digits
        (427383180 * p(797) - 1, 5),    // 339 digits
        (1217763452 * p(601) - 1, 5),   // 257 digits
        (206262090 * p(479) - 1, 5),    // 207 digits
        (463419585 * pow(2, 353) - 1, 5),   // 115 digits
        (96952995 * pow(2, 258) - 1, 5),    // 86 digits
        (9006546615u64 * pow(2, 223) - 1, 5),   // 78 digits
        (2799873605326u64 * p(2371) - 1, 6),    // 1016 digits
        (37488065464u64 * p(1483) - 1, 6),  // 633 digits
        (33692909611u64 * p(977) - 1, 6),   // 417 digits
        (716250935 * p(491) - 1, 6),    // 213 digits
        (620060805 * pow(2, 252) - 1, 6),   // 85 digits
        (505054485 * pow(2, 154) - 1, 6),   // 56 digits
        (82466536397303904u64 * p(1171) - 1, 7),    // 509 digits
        (3931472185692005387730944u128 * p(857) - 1, 7),    // 381 digits
        (14317181455772u64 * p(853) - 1, 7),    // 367 digits
        (162597166369u64 * p(827) - 1, 7),  // 356 digits
        (1178137903623u64 * p(661) - 1, 7), // 291 digits
        (14180848107u64 * p(487) - 1, 7),   // 211 digits
        (472063086 * p(383) + 1236845609, 7),   // 165 digits
        (406605710992u64 * p(349) - 1, 7),  // 153 digits
        (1953370903 * p(151) - 1, 7),   // 69 digits
        (460668119835u64 * pow(2, 101) - 1, 7), // 43 digits
        (27215953890276787u64 * p(37) * pow(2, 3) - 1, 7),  // 31 digits
        (89628063633698570895360u128 * p(593) - 1, 8),  // 265 digits
        (5175268103676u64 * p(557) - 1, 8), // 238 digits
        (2 * 65728407627u64 * p(431) - 1, 8),   // 186 digits
        (1352438530 * p(311) + 5705699, 8), // 135 digits
        (548879116 * p(181) - 1, 8),    // 82 digits
        (1742368093 * p(89) - 1, 8),    // 44 digits
        (1360673835 * pow(2, 50) - 1, 8),   // 25 digits
        (36097525695u64 * pow(2, 41) - 1, 8),   // 23 digits
        (553374939996823808u64 * p(593) - 1, 9),    // 260 digits
        (40912747216912409971130368u128 * p(401) - 1, 9),   // 190 digits
        (65728407627u64 * p(431) - 1, 9),   // 185 digits
        (2093307780 * p(127) - 1, 9),   // 58 digits
        (3696772637099483023015936u128 * p(311) - 1, 10),   // 150 digits
        (380036435653000196587520u128 * p(311) - 1, 10),    // 149 digits
        (1814165079257305081195008u128 * p(307) - 1, 10),   // 148 digits
        (330951321789825381416704u128 * p(307) - 1, 10),    // 147 digits
        (1324846487162u64 * p(223) - 1, 10),    // 99 digits
        (3440034726u64 * p(73) - 1, 10),    // 39 digits
        (1308811392 * p(61) - 1, 10),   // 33 digits
        (i!(73853903764168979088206401473739410396455001112581722569026969860983656346568919) * p(151) - 1, 11),   // 140 digits
        (i!(566002435353389048470195154197633715327639809354150079355350346671860564824949963) * p(89) - 1, 11),   // 116 digits
        (i!(174304836888332595142407951525788751329051227164577255527856958439859830598690304) * p(83) - 1, 11),   // 113 digits
        (i!(488499712314488417016779441191681704321131667381809511540071609780532612839680260) * p(71) - 1, 11),   // 108 digits
        (i!(107386119837124621814971704624900922741439953979550058923273511670890827552543392) * p(59) - 1, 11),   // 102 digits
        (i!(105391885235180642837566579719340498344767363492888467130937411507174806414446905) * p(37) - 1, 11),   // 93 digits
        (4608461 * p(107) + 178414906509839u64, 11),    // 50 digits
        (i!(288320466650346626888267818984974462085357412586437032687304004479168536445314040) * p(83) - 1, 12),   // 113 digits
        (i!(61592551716229060392971860549140211602858978086524024531871935735163762961673908480) * p(71) * -1, 12),    // 111 digits
        (4431659 * p(89) + 440181861259139u64, 12), // 42 digits
        (2 * 1753286498051u64 * p(71) - 1, 12), // 40 digits
        (1307465 * p(79) + 11500298799989u64, 12),  // 37 digits
        (i!(106680560818292299253267832484567360951928953599522278361651385665522443588804123392) * p(61) - 1, 13),    // 107 digits
        (1753286498051u64 * p(71) - 1, 13), // 39 digits
        (2 * i!(27353790674175627273118204975428644651729) + 1, 14),   // 41 digits
        (9510321949318457733566099u128.into(), 14), // 25 digits
        (385931755250345784479u128.into(), 14), // 21 digits
        (14354792166345299956567113728u128 * p(43) - 1, 15),    // 45 digits
        (14366587870229772953764096u128 * p(43) - 1, 15),   // 42 digits
        (i!(27353790674175627273118204975428644651729), 15),   // 41 digits
        (662311489517467124375039u128.into(), 15),  // 24 digits
        (196426752643710966405599u128.into(), 15),  // 24 digits
        (11993367147962683402919u128.into(), 15),   // 23 digits
        (4678714760875524493409u128.into(), 15),    // 22 digits
        (91304653283578934559359u128.into(), 16),   // 23 digits
        (892390227741617675069u128.into(), 16), // 21 digits
        (2759832934171386593519u128.into(), 17),    // 22 digits
    ];

    static ref CC_SECOND_KIND: Vec<(Integer, usize)> = vec![
        // Smallest known Cunningham chain of the second kind
        (16651.into(), 7),  // 5 digits
        (15514861.into(), 8),   // 8 digits
        (857095381.into(), 9),  // 9 digits
        (205528443121u64.into(), 10),   // 12 digits
        (1389122693971u64.into(), 11),  // 13 digits
        (216857744866621u64.into(), 12),    // 15 digits
        (758083947856951u64.into(), 13),    // 15 digits
        (107588900851484911u64.into(), 14), // 18 digits
        (69257563144280941u64.into(), 15),  // 17 digits
        (3203000719597029781u64.into(), 16),    // 19 digits
        (40244844789379926979141u128.into(), 17),   // 23 digits
        (127806074555607670094731u128.into(), 17),  // 24 digits
        (1302312696655394336638441u128.into(), 17), // 25 digits
        (42008163485623434922152331u128.into(), 19),    // 26 digits
        (79910197721667870187016101u128.into(), 19),    // 26 digits
        (117302256313688977973793781u128.into(), 18),   // 27 digits
        (182927793839529342111307801u128.into(), 18),   // 27 digits
        (658189097608811942204322721u128.into(), 18),   // 27 digits
        // Record history
        (3622179275715u64 * pow(2, 256002) + 1, 2), // 77077 digits
        (2570606397u64 * pow(2, 252762) + 1, 2),    // 76099 digits
        (pow(352666770, 8192) + 1, 2),  // 70021 digits
        (556336461 * pow(2, 211355) + 1, 2),    // 63633 digits
        (7775705415u64 * pow(2, 175115) + 1, 2),    // 52725 digits
        (9985628193u64 * pow(2, 171008) + 1, 2),    // 51489 digits
        (129431439657u64 * pow(2, 170171) + 1, 2),  // 51238 digits
        (185688291 * pow(2, 161616) + 1, 2),    // 48660 digits
        (1579755 * pow(2, 158712) + 1, 2),  // 47784 digits
        (648309 * pow(2, 148310) + 1, 2),   // 44652 digits
        (552903 * pow(2, 136156) + 1, 2),   // 40993 digits
        (163221 * pow(2, 124600) + 1, 2),   // 37514 digits
        (532323 * pow(2, 104389) + 1, 2),   // 31430 digits
        (581627055 * pow(2, 93181) + 1, 2), // 28060 digits
        (3853775193u64 * pow(2, 80000) + 1, 2), // 24092 digits
        (1504084599 * pow(2, 78341) + 1, 2),    // 23593 digits
        (863710323 * pow(2, 52588) + 1, 2), // 15840 digits
        (55003425 * pow(2, 50000) + 1, 2),  // 15060 digits
        (164581485 * pow(2, 49800) + 1, 2), // 15000 digits
        (675558849 * pow(2, 40217) + 1, 2), // 12116 digits
        (16769025 * pow(2, 34071) + 1, 2),  // 10264 digits
        (15015 * pow(2, 23870) + 1, 2), // 7190 digits
        (778965587811u64 * pow(2, 36625) - 1, 3),   // 11038 digits
        (914546877 * pow(2, 34772) - 1, 3), // 10477 digits
        (379185609 * pow(2, 27127) - 1, 3), // 8175 digits
        (164210699973u64 * pow(2, 26326) - 1, 3),   // 7937 digits
        (2366867925u64 * pow(2, 17206) + 1, 3), // 5189 digits
        (5040102231u64 * pow(2, 12301) - 1, 3), // 3713 digits
        (268382583 * pow(2, 12294) - 1, 3), // 3710 digits
        (1361835195 * pow(2, 8191) + 1, 3), // 2475 digits
        (1568753260 * p(4673) + 1, 3),  // 2006 digits
        (384205437 * pow(2, 4000) - 1, 3),  // 1213 digits
        (49325406476u64 * p(9811) + 1, 4),  // 4233 digits
        (17285145467u64 * p(6977) + 1, 4),  // 3005 digits
        (35598436282u64 * p(6701) + 1, 4),  // 2878 digits
        (1453501013 * p(4127) + 1, 4),  // 1770 digits
        (153344568 * p(4001) + 1, 4),   // 1711 digits
        (131853904032u64 * p(3061) + 1, 4), // 1313 digits
        (356701232 * p(3041) + 1, 4),   // 1303 digits
        (92406026 * p(1187) + 1, 4),    // 506 digits
        (164285535 * pow(2, 972) + 1, 4),   // 301 digits
        (723592485 * pow(2, 770) + 1, 4),   // 241 digits
        (181439827616655015936u128 * p(4673) + 1, 5),   // 2018 digits
        (6413732664u64 * p(3797) + 1, 5),   // 1630 digits
        (646737879652976640u64 * p(3559) + 1, 5),   // 1535 digits
        (26483492454758573330432u128 * p(3109) + 1, 5), // 1342 digits
        (56185437312u64 * p(3001) + 1, 5),  // 1288 digits
        (80670856865u64 * p(2677) + 1, 5),  // 1140 digits
        (45008010405u64 * p(2621) + 1, 5),  // 1116 digits
        (1719674368 * p(1447) + 1, 5),  // 613 digits
        (496391760 * p(1277) + 325305140161u64, 5), // 540 digits
        (51946113 * p(1193) + 1, 5),    // 509 digits
        (518179995 * pow(2, 308) + 1, 5),   // 102 digits
        (392651625 * pow(2, 222) + 1, 5),   // 76 digits
        (480112483568u64 * p(1511) + 1, 6), // 650 digits
        (37783362904u64 * p(1097) + 1, 6),  // 475 digits
        (703632724 * p(787) + 94265010841u64, 6),   // 336 digits
        (42693782492u64 * p(739) + 1, 6),   // 318 digits
        (2197316072u64 * p(647) + 105063678721u64, 6),  // 279 digits
        (6302319587u64 * p(509) + 1, 6),    // 222 digits
        (1056231420 * p(479) + 1, 6),   // 208 digits
        (388562456 * p(331) + 1, 6),    // 142 digits
        (2 * 305372608 * p(271) + 1, 6),    // 120 digits
        (25802590081726373888u128 * p(1033) + 1, 7),    // 453 digits
        (668302064 * p(593) + 786153598231u64, 7),  // 251 digits
        (414792720846u64 * p(557) + 1, 7),  // 237 digits
        (782350985 * p(503) + 2189997811u64, 7),    // 218 digits
        (2310290388u64 * p(283) + 1, 7),    // 128 digits
        (1701815519 * p(277) + 1, 7),   // 123 digits
        (843616025 * p(193) + 1, 7),    // 87 digits
        (666325605 * pow(2, 60) + 1, 7),    // 27 digits
        (2373007846680317952u64 * p(761) + 1, 8),   // 337 digits
        (112156947439087303442563072u128 * p(491) + 1, 8),  // 230 digits
        (1148424905221u64 * p(509) + 1, 8), // 224 digits
        (177497325593u64 * p(229) + 1, 8),  // 103 digits
        (1831430532 * p(107) + 1, 8),   // 52 digits
        (173129832252242394185728u128 * p(401) + 1, 9), // 187 digits
        (745395266 * p(211) + 1503602101, 9),   // 94 digits
        (1061169280 * p(103) + 1, 9),   // 50 digits
        (43105142 * p(73) + 1, 9),  // 37 digits
        (i!(462437381164406137571238642026500487143562202130164203468923172902534686193803360) * p(127) + 1, 10),  // 130 digits
        (i!(56264173162248110557182990671699794423868532232638543675069282466016594777519178) * p(113) + 1, 10),   // 127 digits
        (i!(124204185879546865064885473789426527077462683918304583642200186747726088560403328) * p(89) + 1, 10),   // 115 digits
        (1070828503293u64 * p(239) + 1, 10),    // 109 digits
        (145683282311u64 * p(181) + 1, 10), // 84 digits
        (3886637 * p(151) + 26473215718951u64, 10), // 66 digits
        (8296886802u64 * p(103) + 1, 10),   // 51 digits
        (341841671431409652891648u128 * p(311) + 1, 11),    // 149 digits
        (19298029794843054654u128 * p(311) + 1, 11),    // 145 digits
        (i!(189431187381152056703213606148620440770958584332732508794815501069120395607727520) * p(71) + 1, 11),   // 108 digits
        (i!(848029410248902405267951124411141542913902774598042414627002939891647628881358680) * p(43) + 1, 11),   // 98 digits
        (i!(244904970375722028798242559069071350723679913437376658289613677305863972540773149) * p(29) + 1, 11),   // 91 digits
        (2 * 13931865163581u64 * p(127) + 1, 11),   // 63 digits
        (2 * (8428860 * p(127) + 212148902055091u64) - 1, 11),  // 56 digits
        (792619264990u64 * p(103) + 1, 11), // 53 digits
        (906644189971753846618980352u128 * p(233) + 1, 12), // 121 digits
        (i!(61592551716229060392971860549140211602858978086524024531871935735163762961673908480) * p(71) * -1, 12),    // 111 digits
        (i!(27514366944545993668422567193822444315682837691915196563994783521784099031989503616) * p(41) + 1, 12), // 97 digits
        (i!(263663326886409378473341387047271336974122837948496277769621396327294641140893808) * p(43) + 1, 12),   // 97 digits
        (13931865163581u64 * p(127) + 1, 12),   // 62 digits
        (8428860 * p(127) + 212148902055091u64, 12),    // 56 digits
        (i!(10756750720700195380397697188448178460115725467111771468875842964723844354555016704) * p(31) + 1, 13), // 94 digits
        (938719 * p(67) + 56461354019071u64, 13),   // 31 digits
        (i!(5819411283298069803200936040662511327268486153212216998535044251830806354124236416) * p(47) + 1, 14),  // 100 digits
        (335898524600734221050749906451371u128.into(), 14), // 33 digits
        (2 * i!(28320350134887132315879689643841) - 1, 14),    // 32 digits
        (2354904873485081880414653783011u128.into(), 14),   // 31 digits
        (2337673907855670908145009878491u128.into(), 14),   // 31 digits
        (20299226100350079536373721u128.into(), 14),    // 26 digits
        (28320350134887132315879689643841u128.into(), 15),  // 32 digits
        (71838292723844326926417601u128.into(), 15),    // 26 digits
        (5830768257311375388822241u128.into(), 15), // 25 digits
        (2817673877915370357723841u128.into(), 15), // 25 digits
        (105998574608115401372161u128.into(), 15),  // 24 digits
        (2 * i!(15745040405007366603151) - 1, 15), // 23 digits
        (54269795934721528591u128.into(), 15),  // 20 digits
        (2 * i!(1540797425367761006138858881) - 1, 16),    // 28 digits
        (4 * i!(658189097608811942204322721) - 3, 16), // 28 digits
        (2368823992523350998418445521u128.into(), 16),  // 28 digits
        (20193491108493165642344881u128.into(), 16),    // 26 digits
        (2 * i!(1302312696655394336638441) - 1, 16),   // 25 digits
        (258296136493222766530021u128.into(), 16),  // 24 digits
        (2 * i!(127806074555607670094731) - 1, 16),    // 24 digits
        (15745040405007366603151u128.into(), 16),   // 23 digits
        (3203000719597029781u128.into(), 16),   // 19 digits
        (1540797425367761006138858881u128.into(), 17),  // 28 digits
        (2 * i!(658189097608811942204322721) - 1, 17), // 28 digits
        (465463467291895470464386321u128.into(), 17),   // 27 digits
        (1302312696655394336638441u128.into(), 17), // 25 digits
        (127806074555607670094731u128.into(), 17),  // 24 digits
        (40244844789379926979141u128.into(), 17),   // 23 digits
        (658189097608811942204322721u128.into(), 18),   // 27 digits
        (182927793839529342111307801u128.into(), 18),   // 27 digits
        (79910197721667870187016101u128.into(), 19),    // 26 digits
        (42008163485623434922152331u128.into(), 19),    // 26 digits
    ];
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum ChainKind {
    First,
    Second,
}

fn cunningham_chain(
    m: &Integer,
    mut length: usize,
    kind: ChainKind,
) -> impl Iterator<Item = Integer> {
    let m = m.clone();

    let mut x = 1;
    std::iter::from_fn(move || {
        if length == 0 {
            return None;
        }

        let m = if x == 1 {
            m.clone()
        } else {
            match kind {
                ChainKind::First => m.clone() * x + x - 1,
                ChainKind::Second => m.clone() * x - (x - 1),
            }
        };
        x *= 2;
        length -= 1;
        Some(m)
    })
}

/// Factorization using primes from famous Cunningham Chains
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CunninghamChainAttack;

impl Attack for CunninghamChainAttack {
    fn name(&self) -> &'static str {
        "cunningham_chain"
    }

    fn run(&self, params: &Parameters, pb: Option<&ProgressBar>) -> Result<Solution, Error> {
        let e = &params.e;
        let n = params.n.as_ref().ok_or(Error::MissingParameters)?;

        if let Some(pb) = pb {
            pb.set_length((CC_FIRST_KIND.len() + CC_SECOND_KIND.len()) as u64);
        }
        for ((m, length), kind) in CC_FIRST_KIND
            .iter()
            .zip([ChainKind::First].iter().cycle())
            .chain(
                CC_SECOND_KIND
                    .iter()
                    .zip([ChainKind::Second].iter().cycle()),
            )
        {
            for p in cunningham_chain(m, *length, *kind) {
                if p > *n {
                    break;
                }
                if n.is_divisible(&p) {
                    let q = n.clone() / &p;
                    return Ok(Solution::new_pk(
                        self.name(),
                        PrivateKey::from_p_q(p, q, e)?,
                    ));
                }
            }
            if let Some(pb) = pb {
                pb.inc(1);
            }
        }
        Err(Error::NotFound)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn small_chain() {
        assert_eq!(
            cunningham_chain(&85864769.into(), 9, ChainKind::First).collect::<Vec<_>>(),
            vec![
                85864769.into(),
                171729539.into(),
                343459079.into(),
                686918159.into(),
                1373836319.into(),
                2747672639u64.into(),
                5495345279u64.into(),
                10990690559u64.into(),
                21981381119u64.into(),
            ] as Vec<Integer>
        );
    }

    #[test]
    fn attack() {
        let p = Integer::from(10990690559u64);
        let q = Integer::from(21981381119u64);

        let params = Parameters {
            n: Some(p.clone() * &q),
            ..Default::default()
        };
        let solution = CunninghamChainAttack.run(&params, None).unwrap();
        let pk = solution.pk.unwrap();

        assert_eq!(pk.p(), p);
        assert_eq!(pk.q(), q);
    }
}