请输入您要查询的字词:

 

单词 ExamplesOfTheFermatMethodOnAFewIntegers
释义

examples of the Fermat method on a few integers


Take n=2039183. The square root is approximately 1428, so that’s what we set our iterator’s initial state to. The test cap is 339865.

At i=1428, we find that 14282-2039183=1, clearly an integer.

Then, 1428-1=1427 and 1428+1=1429. By multiplicationPlanetmathPlanetmath, we verify that 2039183=14271429, indeed. It is the product of a twin primeMathworldPlanetmath. By trial divisionMathworldPlanetmath, this would have taken 225 test divisions.

However, there are integers for which trial division performs much better than the Fermat method. For example, take n=1411041. Our iterator starts at 1188 and the test cap is 235175.

At i=1188, we find that 11882-141104117.4068952. Similar frustration at 1189, 1190, etc.

It’s not until we get to i=235175 that we finally get 2351752-1411041=235172.

Then, 235175-235172=3, and 235175+235172=470347, and we verify that indeed 3470347=2039183. This took 233987 instances of squaring, subtraction and square root extraction, which would have taken just 196 test divisions in trial division.

How about 4393547637856664251490043044051018234292171475232959? The square root is approximately 6628384145368058140794809 and the test cap is 732257939642777375248340507341836372382028579205495. At worst, the Fermat method could take as many as 732257939642777375248340500713452227013970438410686 instances of squaring, subtraction and square root extraction to give a result. Clearly a more sophisticated method is needed to factorize an integer of this magnitude.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/3 13:48:43