ユークリッドの互除法のパワー

これについては，約分がらみでいろいろ書いたが．＞互除法で検索

日常の約分程度では，桁数がたいしたことはない．今日は巨大数の最大公約数．

49461452598938785494314994799599149312722195048706571288833609737846761389207
と
51563219734746742542718349822659719885743944234989846041303683354097028855491
の最大公約数は
184006271650631966286938034234608785633
となった．

もし，　
49461452598938785494314994799599149312722195048706571288833609737846761389207 を普通に，1,3,5,7,9,11,13,15,17,19・・・と奇数で割り続け，
184006271650631966286938034234608785633
に到達するには，
184006271650631966286938034234608785633÷2=9.200×10^37
回の割り算になる．
1秒で1兆回＝1テラ回の割り算で，（となるとパソコンのクロックは数テラHz＝数千GHz の性能）
9.200×10^25 秒 = 2.92×10^18 年
かかる．宇宙が始まって，150億年とすると，その長さの
1.94×10^8 倍 = 2億倍
の年数がかかる．
それが，ユークリッドの互除法では，以下のように74回目で求めることができる．

素因数をみつけるには，単純な割り算以上に効率的な方法が開発されているが，劇的に速いものはない．この，巨大整数の素因数分解の難しさが，インターネットの暗号の安全性につながっている．この例の素因数が39桁だが，インターネットの RSA暗号では150桁や，300桁のものが利用されている．

1つの数の素因数分解は困難だが，2数の最大公約数を求めるなら，ユークリッドの互除法を用いるとたやすい．それこそ，「ブログに書き留められるくらいの量」で片付いてしまう程度の簡単なものになる．これがユークリッドの互除法のパワーである．
＞くろべえ「互除法」関連の記事

1.
51563219734746742542718349822659719885743944234989846041303683354097028855491
- 1×49461452598938785494314994799599149312722195048706571288833609737846761389207
= 2101767135807957048403355023060570573021749186283274752470073616250267466284

2.
49461452598938785494314994799599149312722195048706571288833609737846761389207
- 23×2101767135807957048403355023060570573021749186283274752470073616250267466284
= 1120808475355773381037829269206026133221963764191251982021916564090609664675

3.
2101767135807957048403355023060570573021749186283274752470073616250267466284
- 1×1120808475355773381037829269206026133221963764191251982021916564090609664675
= 980958660452183667365525753854544439799785422092022770448157052159657801609

4.
1120808475355773381037829269206026133221963764191251982021916564090609664675
- 1×980958660452183667365525753854544439799785422092022770448157052159657801609
= 139849814903589713672303515351481693422178342099229211573759511930951863066

5.
980958660452183667365525753854544439799785422092022770448157052159657801609
- 7×139849814903589713672303515351481693422178342099229211573759511930951863066
= 2009956127055671659401146394172585844537027397418289431840468642994760147

6.
139849814903589713672303515351481693422178342099229211573759511930951863066
- 69×2009956127055671659401146394172585844537027397418289431840468642994760147
= 1162842136748369173624414153573270149123451677367240776767175564313412923

7.
2009956127055671659401146394172585844537027397418289431840468642994760147
- 1×1162842136748369173624414153573270149123451677367240776767175564313412923
= 847113990307302485776732240599315695413575720051048655073293078681347224

8.
1162842136748369173624414153573270149123451677367240776767175564313412923
- 1×847113990307302485776732240599315695413575720051048655073293078681347224
= 315728146441066687847681912973954453709875957316192121693882485632065699

9.
847113990307302485776732240599315695413575720051048655073293078681347224
- 2×315728146441066687847681912973954453709875957316192121693882485632065699
= 215657697425169110081368414651406787993823805418664411685528107417215826

10.
315728146441066687847681912973954453709875957316192121693882485632065699
- 1×215657697425169110081368414651406787993823805418664411685528107417215826
= 100070449015897577766313498322547665716052151897527710008354378214849873

11.
215657697425169110081368414651406787993823805418664411685528107417215826
- 2×100070449015897577766313498322547665716052151897527710008354378214849873
= 15516799393373954548741418006311456561719501623608991668819350987516080

12.
100070449015897577766313498322547665716052151897527710008354378214849873
- 6×15516799393373954548741418006311456561719501623608991668819350987516080
= 6969652655653850473864990284678926345735142155873759995438272289753393

13.
15516799393373954548741418006311456561719501623608991668819350987516080
- 2×6969652655653850473864990284678926345735142155873759995438272289753393
= 1577494082066253601011437436953603870249217311861471677942806408009294

14.
6969652655653850473864990284678926345735142155873759995438272289753393
- 4×1577494082066253601011437436953603870249217311861471677942806408009294
= 659676327388836069819240536864510864738272908427873283667046657716217

15.
1577494082066253601011437436953603870249217311861471677942806408009294
- 2×659676327388836069819240536864510864738272908427873283667046657716217
= 258141427288581461372956363224582140772671495005725110608713092576860

16.
659676327388836069819240536864510864738272908427873283667046657716217
- 2×258141427288581461372956363224582140772671495005725110608713092576860
= 143393472811673147073327810415346583192929918416423062449620472562497

17.
258141427288581461372956363224582140772671495005725110608713092576860
- 1×143393472811673147073327810415346583192929918416423062449620472562497
= 114747954476908314299628552809235557579741576589302048159092620014363

18.
143393472811673147073327810415346583192929918416423062449620472562497
- 1×114747954476908314299628552809235557579741576589302048159092620014363
= 28645518334764832773699257606111025613188341827121014290527852548134

19.
114747954476908314299628552809235557579741576589302048159092620014363 - 4×28645518334764832773699257606111025613188341827121014290527852548134
= 165881137848983204831522384791455126988209280817990996981209821827

20.
28645518334764832773699257606111025613188341827121014290527852548134
- 172×165881137848983204831522384791455126988209280817990996981209821827
= 113962624739721542677407421980743771216345526426562809759763193890

21.
165881137848983204831522384791455126988209280817990996981209821827
- 1×113962624739721542677407421980743771216345526426562809759763193890
= 51918513109261662154114962810711355771863754391428187221446627937

22.
113962624739721542677407421980743771216345526426562809759763193890
- 2×51918513109261662154114962810711355771863754391428187221446627937
= 10125598521198218369177496359321059672618017643706435316869938016

23.
51918513109261662154114962810711355771863754391428187221446627937
- 5×10125598521198218369177496359321059672618017643706435316869938016
= 1290520503270570308227481014106057408773666172896010637096937857

24.
10125598521198218369177496359321059672618017643706435316869938016
- 7×1290520503270570308227481014106057408773666172896010637096937857
= 1091954998304226211585129260578657811202354433434360857191373017

25.
1290520503270570308227481014106057408773666172896010637096937857
- 1×1091954998304226211585129260578657811202354433434360857191373017
= 198565504966344096642351753527399597571311739461649779905564840

26.
1091954998304226211585129260578657811202354433434360857191373017
- 5×198565504966344096642351753527399597571311739461649779905564840
= 99127473472505728373370492941659823345795736126111957663548817

27.
198565504966344096642351753527399597571311739461649779905564840
- 2×99127473472505728373370492941659823345795736126111957663548817
= 310558021332639895610767644079950879720267209425864578467206

28.
99127473472505728373370492941659823345795736126111957663548817
- 319×310558021332639895610767644079950879720267209425864578467206
= 59464667393601673535614480155492715030496319261157132510103

29.
310558021332639895610767644079950879720267209425864578467206
- 5×59464667393601673535614480155492715030496319261157132510103
= 13234684364631527932695243302487304567785613120078915916691

30.
59464667393601673535614480155492715030496319261157132510103
- 4×13234684364631527932695243302487304567785613120078915916691
= 6525929935075561804833506945543496759353866780841468843339

31.
13234684364631527932695243302487304567785613120078915916691
- 2×6525929935075561804833506945543496759353866780841468843339
= 182824494480404323028229411400311049077879558395978230013

32.
6525929935075561804833506945543496759353866780841468843339
- 35×182824494480404323028229411400311049077879558395978230013
= 127072628261410498845477546532610041628082236982230792884

33.
182824494480404323028229411400311049077879558395978230013
- 1×127072628261410498845477546532610041628082236982230792884
= 55751866218993824182751864867701007449797321413747437129

34.
127072628261410498845477546532610041628082236982230792884
- 2×55751866218993824182751864867701007449797321413747437129
= 15568895823422850479973816797208026728487594154735918626

35.
55751866218993824182751864867701007449797321413747437129
- 3×15568895823422850479973816797208026728487594154735918626
= 9045178748725272742830414476076927264334538949539681251

36.
15568895823422850479973816797208026728487594154735918626
- 6×9045178748725272742830414476076927264334538949539681251
= 6523717074697577737143402321131099464153055205196237375

37.
9045178748725272742830414476076927264334538949539681251
- 1×6523717074697577737143402321131099464153055205196237375
= 2521461674027695005687012154945827800181483744343443876

38.
6523717074697577737143402321131099464153055205196237375
- 2×2521461674027695005687012154945827800181483744343443876
= 1480793726642187725769378011239443863790087716509349623

39.
2521461674027695005687012154945827800181483744343443876
- 1×1480793726642187725769378011239443863790087716509349623
= 1040667947385507279917634143706383936391396027834094253

40.
1480793726642187725769378011239443863790087716509349623
- 1×1040667947385507279917634143706383936391396027834094253
= 440125779256680445851743867533059927398691688675255370

41.
1040667947385507279917634143706383936391396027834094253
- 2×440125779256680445851743867533059927398691688675255370
= 160416388872146388214146408640264081594012650483583513

42.
440125779256680445851743867533059927398691688675255370
- 2×160416388872146388214146408640264081594012650483583513
= 119293001512387669423451050252531764210666387708088344

43.
160416388872146388214146408640264081594012650483583513
- 1×119293001512387669423451050252531764210666387708088344
= 41123387359758718790695358387732317383346262775495169

44.
119293001512387669423451050252531764210666387708088344
- 2×41123387359758718790695358387732317383346262775495169
= 37046226792870231842060333477067129443973862157098006

45.
41123387359758718790695358387732317383346262775495169
- 1×37046226792870231842060333477067129443973862157098006
= 4077160566888486948635024910665187939372400618397163

46.
37046226792870231842060333477067129443973862157098006
- 9×4077160566888486948635024910665187939372400618397163
= 351781690873849304345109281080437989622256591523539

47.
4077160566888486948635024910665187939372400618397163
- 11×351781690873849304345109281080437989622256591523539
= 207561967276144600838822818780370053527578111638234

48.
351781690873849304345109281080437989622256591523539
- 1×207561967276144600838822818780370053527578111638234
= 144219723597704703506286462300067936094678479885305

49.
207561967276144600838822818780370053527578111638234
- 1×144219723597704703506286462300067936094678479885305a = 63342243678439897332536356480302117432899631752929b

50.
144219723597704703506286462300067936094678479885305a - 2×63342243678439897332536356480302117432899631752929b = 17535236240824908841213749339463701228879216379447

51.
63342243678439897332536356480302117432899631752929b - 3×17535236240824908841213749339463701228879216379447
= 10736534955965170808895108461911013746261982614588

52.
17535236240824908841213749339463701228879216379447
- 1×10736534955965170808895108461911013746261982614588
= 6798701284859738032318640877552687482617233764859

53.
10736534955965170808895108461911013746261982614588
- 1×6798701284859738032318640877552687482617233764859
= 3937833671105432776576467584358326263644748849729

54.
6798701284859738032318640877552687482617233764859
- 1×3937833671105432776576467584358326263644748849729
= 2860867613754305255742173293194361218972484915130

55.
3937833671105432776576467584358326263644748849729
- 1×2860867613754305255742173293194361218972484915130
= 1076966057351127520834294291163965044672263934599

56.
2860867613754305255742173293194361218972484915130
- 2×1076966057351127520834294291163965044672263934599
= 706935499052050214073584710866431129627957045932

57.
1076966057351127520834294291163965044672263934599
- 1×706935499052050214073584710866431129627957045932
= 370030558299077306760709580297533915044306888667

58.
706935499052050214073584710866431129627957045932
- 1×370030558299077306760709580297533915044306888667
= 336904940752972907312875130568897214583650157265

59.
370030558299077306760709580297533915044306888667
- 1×336904940752972907312875130568897214583650157265
= 33125617546104399447834449728636700460656731402

60.
336904940752972907312875130568897214583650157265
- 10×33125617546104399447834449728636700460656731402
= 5648765291928912834530633282530209977082843245

61.
33125617546104399447834449728636700460656731402
- 5×5648765291928912834530633282530209977082843245
= 4881791086459835275181283315985650575242515177

62.
5648765291928912834530633282530209977082843245
- 1×4881791086459835275181283315985650575242515177
= 766974205469077559349349966544559401840328068

63.
4881791086459835275181283315985650575242515177
- 6×766974205469077559349349966544559401840328068
= 279945853645369919085183516718294164200546769

64.
766974205469077559349349966544559401840328068
- 2×279945853645369919085183516718294164200546769
= 207082498178337721178982933107971073439234530

65.
279945853645369919085183516718294164200546769
- 1×207082498178337721178982933107971073439234530
= 72863355467032197906200583610323090761312239

66.
207082498178337721178982933107971073439234530
- 2×72863355467032197906200583610323090761312239
= 61355787244273325366581765887324891916610052

67.
72863355467032197906200583610323090761312239
- 161355787244273325366581765887324891916610052
= 11507568222758872539618817722998198844702187

68.
161355787244273325366581765887324891916610052
- 5×11507568222758872539618817722998198844702187
= 3817946130478962668487677272333897693099117

69.
11507568222758872539618817722998198844702187
- 3×3817946130478962668487677272333897693099117
= 53729831321984534155785905996505765404836

70.
11507568222758872539618817722998198844702187
- 71×53729831321984534155785905996505765404836
= 3128106618060743426877946581988349355761

71.
53729831321984534155785905996505765404836
- 17×3128106618060743426877946581988349355761
= 552018814951895898860814102703826356899

72.
3128106618060743426877946581988349355761
- 5×552018814951895898860814102703826356899
= 368012543301263932573876068469217571266

73.
552018814951895898860814102703826356899
- 1×368012543301263932573876068469217571266
= 184006271650631966286938034234608785633

74
368012543301263932573876068469217571266
- 2×184006271650631966286938034234608785633 = 0

よって，最大公約数は
184006271650631966286938034234608785633

したがって，
49461452598938785494314994799599149312722195048706571288833609737846761389207
= 184006271650631966286938034234608785633×268803080217015586760804524423491087479
51563219734746742542718349822659719885743944234989846041303683354097028855491
= 184006271650631966286938034234608785633×280225338365903733999847582749814689827
と分解できる．実はこれらは素数なので，素因数分解になっている．