|
[原创]整数分解随笔(7)
一个求乘法逆元的方法 以下介绍一个素数求逆元的方法,与其它四种常见的求乘法逆元有所不同,主要是使用除数的积来求逆,供大家参考,如有不足,欢迎大家批评指正。 求a在p中的逆,其中p为素数,按以下公式求余: a*r1≡q1(mod p) 其中a*r1>p, a>q1 q1*r2≡q2(mod p) 其中q1*r2>p, q1>q2 q2*r3≡q3(mod p) 其中q2*r3>p, q2>q3 . . . q(n-1)*rn≡1(mod p) 其中q(n-1)*rn>p, q(n-1)>1 以上相乘得: a*r*q1*r2*...q(n-1)*rn≡q1*q2*...1(mod p) 因假设p为素数,所以上式两边除q1*q2*...得: a*(r1*r2...rn)≡=1(mod p) 即:a与r1*r2....*rn在p中互逆 例如 求24在83的逆元: 24*4≡13(mod 83) 13*7≡8 (mod 83) 8*11≡5 (mod 83) 5*17≡2 (mod 83) 2*42≡1 (mod 83) 4*7*11*17*42≡45 (mod 83) 即24的逆元为45 求25在83的逆元: 25*4≡17(mod 83) 17*5≡2 (mod 83) 2*24≡1 (mod 83) 4*5*42≡10 (mod 83) 即25的逆元为10 求25在131的逆元: 25*6≡19 (mod 131) 19*7≡2 (mod 131) 2*66≡1 (mod 131) 6*7*66≡21 (mod 131) 即25的逆元为21 求34在131的逆元: 34*4≡5 (mod 131) 5*27≡4 (mod 131) 4*33≡1 (mod 131) 4*27*33≡27 (mod 131) 即34的逆元为27 程序如下: #include <stdio.h> main() { unsigned long a,b,n; unsigned long r,q,res; printf("输入两个数:\n"); scanf("%ld%ld", &a, &n); b=a; if( a > n ) { a=n; n=b; } res=1; while(1) { r=n/a; r++; q=r*a-n; res=(res*r)%n; if( q == 1 ) { printf("%ld的逆%ld\n",b,res); printf("%ld*%ld=%ld(mod %ld)\n",b,res,(res*b)%n,n); break; } if( q == 0 || q == a ) { printf("%ld存在因子%ld\n",n,a); break; } a=q; } } |
|
[原创]整数分解随笔(7)
最近根据以上原理,自己设计了一个算法,该算法的以sqrt(n)作为起点,乘以2、3、5、7,放入一组数组中,再对这组数组进行比较(比较的方法与冒泡排序相似),看是否在设定的范围,在范围内,即分解该数,经在windows用DEV C++和red hat 7.5编译通过,经过测试,在2^63内的数,基本上能秒分解,与pollard_rho算法分解速度差不多,附件为C的源码(上传在正文中),共大家参考,如果有兴趣,可以共同探讨,研究更好、更快的整数分解的算法
最后于 2019-11-17 10:41
被songls编辑
,原因: 修改一下表述
|
|
[原创]整数分解随笔(一个算法)
三、对pollard rho改造 由于pollrad rho分解算法只对一个数进行判断是否存在n的因子,可以使用上述算法对pollrad rho进行改造,让其在一段范围内进行查找n的因子,提高一定的效率,当然如果改造有什么问题,欢迎大家指正,谢谢! 先看一下,原始的pollrad rho算法: long Pollard_rho(long n, int c) { long i, k, x, y, d; srand(time(NULL)); i = 1; k = 2; x = rand() % n; y = x; while (true) { i++; x = (mod_mult(x, x, n) + c) % n; d = gcd(y - x, n); if (d > 1 && d < n) return d; if (y == x) /*该数已经出现过,直接返回即可 */ return n; if (i == k) { y = x; k = k << 1; } } } 主要改造在: d = gcd(y - x, n); 先按上述算法写一个函数“ long getfac( long a, long n,int num) { long t; long res,b; int i,m; b=(a*a)%n; t=sqrt(b); if( (t*t)==b && (b*b) != a ) return gcd(a+b,n); res=b; m=1; for( i=0 ; i<num ; i++) { b=b-m; res=(res*b)%n; if( res == 0 ) return gcd( b , n ); m=m+2; } return gcd(res,n); } long Pollard_rho(long n, int c, int num) { long i, k, x, y, d; srand(time(NULL)); i = 1; k = 2; x = rand() % n; y = x; while (true) { i++; x = (mod_mult(x, x, n) + c) % n; /*d = gcd(y - x, n);*/ d=getfac( y-x,n,num); if (d > 1 && d < n) return d; if (y == x) /*该数已经出现过,直接返回即可 */ return n; if (i == k) { y = x; k = k << 1; } } } 在Pollard_rho函数中,加入一个次数的传入值,把d = gcd(y - x, n);修改为d=getfac( y-x,n,num);,既不改变Pollrad rho原先的判断,而且加大了一段范围的判断。 |
|
[原创]整数分解随笔(六)
三、连续两整数之和与之积的性质 |
|
[原创]整数分解随笔(六)
二、相邻两平方剩余的乘法 |
|
[原创]整数分解随笔(五)
894^2≡906 , 895^2≡648 , 896^2≡392 , 897^2≡138 , 898^2≡1933 , 899^2≡1683 , 900^2≡1435 , 901^2≡1189 , 902^2≡945 , 903^2≡703 , 904^2≡463 , 905^2≡225 , 906^2≡2036 , 907^2≡1802 , 908^2≡1570 , 909^2≡1340 , 910^2≡1112 , 911^2≡886 , 912^2≡662 , 913^2≡440 , 914^2≡220 , 915^2≡2 , 916^2≡1833 , 917^2≡1619 , 918^2≡1407 , 919^2≡1197 , 920^2≡989 , 921^2≡783 , 922^2≡579 , 923^2≡377 , 924^2≡177 , 925^2≡2026 , 926^2≡1830 , 927^2≡1636 , 928^2≡1444 , 929^2≡1254 , 930^2≡1066 , 931^2≡880 , 932^2≡696 , 933^2≡514 , 934^2≡334 , 935^2≡156 , 936^2≡2027 , 937^2≡1853 , 938^2≡1681 , 939^2≡1511 , 940^2≡1343 , 941^2≡1177 , 942^2≡1013 , 943^2≡851 , 944^2≡691 , 945^2≡533 , 946^2≡377 , 947^2≡223 , 948^2≡71 , 949^2≡1968 , 950^2≡1820 , 951^2≡1674 , 952^2≡1530 , 953^2≡1388 , 954^2≡1248 , 955^2≡1110 , 956^2≡974 , 957^2≡840 , 958^2≡708 , 959^2≡578 , 960^2≡450 , 961^2≡324 , 962^2≡200 , 963^2≡78 , 964^2≡2005 , 965^2≡1887 , 966^2≡1771 , 967^2≡1657 , 968^2≡1545 , 969^2≡1435 , 970^2≡1327 , 971^2≡1221 , 972^2≡1117 , 973^2≡1015 , 974^2≡915 , 975^2≡817 , 976^2≡721 , 977^2≡627 , 978^2≡535 , 979^2≡445 , 980^2≡357 , 981^2≡271 , 982^2≡187 , 983^2≡105 , 984^2≡25 , 985^2≡1994 , 986^2≡1918 , 987^2≡1844 , 988^2≡1772 , 989^2≡1702 , 990^2≡1634 , 991^2≡1568 , 992^2≡1504 , 993^2≡1442 , 994^2≡1382 , 995^2≡1324 , 996^2≡1268 , 997^2≡1214 , 998^2≡1162 , 999^2≡1112 , 1000^2≡1064 , 1001^2≡1018 , 1002^2≡974 , 1003^2≡932 , 1004^2≡892 , 1005^2≡854 , 1006^2≡818 , 1007^2≡784 , 1008^2≡752 , 1009^2≡722 , 1010^2≡694 , 1011^2≡668 , 1012^2≡644 , 1013^2≡622 , 1014^2≡602 , 1015^2≡584 , 1016^2≡568 , 1017^2≡554 , 1018^2≡542 , 1019^2≡532 , 1020^2≡524 , 1021^2≡518 , 1022^2≡514 , 1023^2≡512 , |
|
[原创]整数分解随笔(五)
662^2≡186 , 663^2≡1511 , 664^2≡791 , 665^2≡73 , 666^2≡1404 , 667^2≡690 , 668^2≡2025 , 669^2≡1315 , 670^2≡607 , 671^2≡1948 , 672^2≡1244 , 673^2≡542 , 674^2≡1889 , 675^2≡1191 , 676^2≡495 , 677^2≡1848 , 678^2≡1156 , 679^2≡466 , 680^2≡1825 , 681^2≡1139 , 682^2≡455 , 683^2≡1820 , 684^2≡1140 , 685^2≡462 , 686^2≡1833 , 687^2≡1159 , 688^2≡487 , 689^2≡1864 , 690^2≡1196 , 691^2≡530 , 692^2≡1913 , 693^2≡1251 , 694^2≡591 , 695^2≡1980 , 696^2≡1324 , 697^2≡670 , 698^2≡18 , 699^2≡1415 , 700^2≡767 , 701^2≡121 , 702^2≡1524 , 703^2≡882 , 704^2≡242 , 705^2≡1651 , 706^2≡1015 , 707^2≡381 , 708^2≡1796 , 709^2≡1166 , 710^2≡538 , 711^2≡1959 , 712^2≡1335 , 713^2≡713 , 714^2≡93 , 715^2≡1522 , 716^2≡906 , 717^2≡292 , 718^2≡1727 , 719^2≡1117 , 720^2≡509 , 721^2≡1950 , 722^2≡1346 , 723^2≡744 , 724^2≡144 , 725^2≡1593 , 726^2≡997 , 727^2≡403 , 728^2≡1858 , 729^2≡1268 , 730^2≡680 , 731^2≡94 , 732^2≡1557 , 733^2≡975 , 734^2≡395 , 735^2≡1864 , 736^2≡1288 , 737^2≡714 , 738^2≡142 , 739^2≡1619 , 740^2≡1051 , 741^2≡485 , 742^2≡1968 , 743^2≡1406 , 744^2≡846 , 745^2≡288 , 746^2≡1779 , 747^2≡1225 , 748^2≡673 , 749^2≡123 , 750^2≡1622 , 751^2≡1076 , 752^2≡532 , 753^2≡2037 , 754^2≡1497 , 755^2≡959 , 756^2≡423 , 757^2≡1936 , 758^2≡1404 , 759^2≡874 , 760^2≡346 , 761^2≡1867 , 762^2≡1343 , 763^2≡821 , 764^2≡301 , 765^2≡1830 , 766^2≡1314 , 767^2≡800 , 768^2≡288 , 769^2≡1825 , 770^2≡1317 , 771^2≡811 , 772^2≡307 , 773^2≡1852 , 774^2≡1352 , 775^2≡854 , 776^2≡358 , 777^2≡1911 , 778^2≡1419 , 779^2≡929 , 780^2≡441 , 781^2≡2002 , 782^2≡1518 , 783^2≡1036 , 784^2≡556 , 785^2≡78 , 786^2≡1649 , 787^2≡1175 , 788^2≡703 , 789^2≡233 , 790^2≡1812 , 791^2≡1346 , 792^2≡882 , 793^2≡420 , 794^2≡2007 , 795^2≡1549 , 796^2≡1093 , 797^2≡639 , 798^2≡187 , 799^2≡1784 , 800^2≡1336 , 801^2≡890 , 802^2≡446 , 803^2≡4 , 804^2≡1611 , 805^2≡1173 , 806^2≡737 , 807^2≡303 , 808^2≡1918 , 809^2≡1488 , 810^2≡1060 , 811^2≡634 , 812^2≡210 , 813^2≡1835 , 814^2≡1415 , 815^2≡997 , 816^2≡581 , 817^2≡167 , 818^2≡1802 , 819^2≡1392 , 820^2≡984 , 821^2≡578 , 822^2≡174 , 823^2≡1819 , 824^2≡1419 , 825^2≡1021 , 826^2≡625 , 827^2≡231 , 828^2≡1886 , 829^2≡1496 , 830^2≡1108 , 831^2≡722 , 832^2≡338 , 833^2≡2003 , 834^2≡1623 , 835^2≡1245 , 836^2≡869 , 837^2≡495 , 838^2≡123 , 839^2≡1800 , 840^2≡1432 , 841^2≡1066 , 842^2≡702 , 843^2≡340 , 844^2≡2027 , 845^2≡1669 , 846^2≡1313 , 847^2≡959 , 848^2≡607 , 849^2≡257 , 850^2≡1956 , 851^2≡1610 , 852^2≡1266 , 853^2≡924 , 854^2≡584 , 855^2≡246 , 856^2≡1957 , 857^2≡1623 , 858^2≡1291 , 859^2≡961 , 860^2≡633 , 861^2≡307 , 862^2≡2030 , 863^2≡1708 , 864^2≡1388 , 865^2≡1070 , 866^2≡754 , 867^2≡440 , 868^2≡128 , 869^2≡1865 , 870^2≡1557 , 871^2≡1251 , 872^2≡947 , 873^2≡645 , 874^2≡345 , 875^2≡47 , 876^2≡1798 , 877^2≡1504 , 878^2≡1212 , 879^2≡922 , 880^2≡634 , 881^2≡348 , 882^2≡64 , 883^2≡1829 , 884^2≡1549 , 885^2≡1271 , 886^2≡995 , 887^2≡721 , 888^2≡449 , 889^2≡179 , 890^2≡1958 , 891^2≡1692 , 892^2≡1428 , 893^2≡1166 , |
|
[原创]整数分解随笔(五)
354^2≡449 , 355^2≡1158 , 356^2≡1869 , 357^2≡535 , 358^2≡1250 , 359^2≡1967 , 360^2≡639 , 361^2≡1360 , 362^2≡36 , 363^2≡761 , 364^2≡1488 , 365^2≡170 , 366^2≡901 , 367^2≡1634 , 368^2≡322 , 369^2≡1059 , 370^2≡1798 , 371^2≡492 , 372^2≡1235 , 373^2≡1980 , 374^2≡680 , 375^2≡1429 , 376^2≡133 , 377^2≡886 , 378^2≡1641 , 379^2≡351 , 380^2≡1110 , 381^2≡1871 , 382^2≡587 , 383^2≡1352 , 384^2≡72 , 385^2≡841 , 386^2≡1612 , 387^2≡338 , 388^2≡1113 , 389^2≡1890 , 390^2≡622 , 391^2≡1403 , 392^2≡139 , 393^2≡924 , 394^2≡1711 , 395^2≡453 , 396^2≡1244 , 397^2≡2037 , 398^2≡785 , 399^2≡1582 , 400^2≡334 , 401^2≡1135 , 402^2≡1938 , 403^2≡696 , 404^2≡1503 , 405^2≡265 , 406^2≡1076 , 407^2≡1889 , 408^2≡657 , 409^2≡1474 , 410^2≡246 , 411^2≡1067 , 412^2≡1890 , 413^2≡668 , 414^2≡1495 , 415^2≡277 , 416^2≡1108 , 417^2≡1941 , 418^2≡729 , 419^2≡1566 , 420^2≡358 , 421^2≡1199 , 422^2≡2042 , 423^2≡840 , 424^2≡1687 , 425^2≡489 , 426^2≡1340 , 427^2≡146 , 428^2≡1001 , 429^2≡1858 , 430^2≡670 , 431^2≡1531 , 432^2≡347 , 433^2≡1212 , 434^2≡32 , 435^2≡901 , 436^2≡1772 , 437^2≡598 , 438^2≡1473 , 439^2≡303 , 440^2≡1182 , 441^2≡16 , 442^2≡899 , 443^2≡1784 , 444^2≡624 , 445^2≡1513 , 446^2≡357 , 447^2≡1250 , 448^2≡98 , 449^2≡995 , 450^2≡1894 , 451^2≡748 , 452^2≡1651 , 453^2≡509 , 454^2≡1416 , 455^2≡278 , 456^2≡1189 , 457^2≡55 , 458^2≡970 , 459^2≡1887 , 460^2≡759 , 461^2≡1680 , 462^2≡556 , 463^2≡1481 , 464^2≡361 , 465^2≡1290 , 466^2≡174 , 467^2≡1107 , 468^2≡2042 , 469^2≡932 , 470^2≡1871 , 471^2≡765 , 472^2≡1708 , 473^2≡606 , 474^2≡1553 , 475^2≡455 , 476^2≡1406 , 477^2≡312 , 478^2≡1267 , 479^2≡177 , 480^2≡1136 , 481^2≡50 , 482^2≡1013 , 483^2≡1978 , 484^2≡898 , 485^2≡1867 , 486^2≡791 , 487^2≡1764 , 488^2≡692 , 489^2≡1669 , 490^2≡601 , 491^2≡1582 , 492^2≡518 , 493^2≡1503 , 494^2≡443 , 495^2≡1432 , 496^2≡376 , 497^2≡1369 , 498^2≡317 , 499^2≡1314 , 500^2≡266 , 501^2≡1267 , 502^2≡223 , 503^2≡1228 , 504^2≡188 , 505^2≡1197 , 506^2≡161 , 507^2≡1174 , 508^2≡142 , 509^2≡1159 , 510^2≡131 , 511^2≡1152 , 512^2≡128 , 513^2≡1153 , 514^2≡133 , 515^2≡1162 , 516^2≡146 , 517^2≡1179 , 518^2≡167 , 519^2≡1204 , 520^2≡196 , 521^2≡1237 , 522^2≡233 , 523^2≡1278 , 524^2≡278 , 525^2≡1327 , 526^2≡331 , 527^2≡1384 , 528^2≡392 , 529^2≡1449 , 530^2≡461 , 531^2≡1522 , 532^2≡538 , 533^2≡1603 , 534^2≡623 , 535^2≡1692 , 536^2≡716 , 537^2≡1789 , 538^2≡817 , 539^2≡1894 , 540^2≡926 , 541^2≡2007 , 542^2≡1043 , 543^2≡81 , 544^2≡1168 , 545^2≡210 , 546^2≡1301 , 547^2≡347 , 548^2≡1442 , 549^2≡492 , 550^2≡1591 , 551^2≡645 , 552^2≡1748 , 553^2≡806 , 554^2≡1913 , 555^2≡975 , 556^2≡39 , 557^2≡1152 , 558^2≡220 , 559^2≡1337 , 560^2≡409 , 561^2≡1530 , 562^2≡606 , 563^2≡1731 , 564^2≡811 , 565^2≡1940 , 566^2≡1024 , 567^2≡110 , 568^2≡1245 , 569^2≡335 , 570^2≡1474 , 571^2≡568 , 572^2≡1711 , 573^2≡809 , 574^2≡1956 , 575^2≡1058 , 576^2≡162 , 577^2≡1315 , 578^2≡423 , 579^2≡1580 , 580^2≡692 , 581^2≡1853 , 582^2≡969 , 583^2≡87 , 584^2≡1254 , 585^2≡376 , 586^2≡1547 , 587^2≡673 , 588^2≡1848 , 589^2≡978 , 590^2≡110 , 591^2≡1291 , 592^2≡427 , 593^2≡1612 , 594^2≡752 , 595^2≡1941 , 596^2≡1085 , 597^2≡231 , 598^2≡1426 , 599^2≡576 , 600^2≡1775 , 601^2≡929 , 602^2≡85 , 603^2≡1290 , 604^2≡450 , 605^2≡1659 , 606^2≡823 , 607^2≡2036 , 608^2≡1204 , 609^2≡374 , 610^2≡1593 , 611^2≡767 , 612^2≡1990 , 613^2≡1168 , 614^2≡348 , 615^2≡1577 , 616^2≡761 , 617^2≡1994 , 618^2≡1182 , 619^2≡372 , 620^2≡1611 , 621^2≡805 , 622^2≡1 , 623^2≡1246 , 624^2≡446 , 625^2≡1695 , 626^2≡899 , 627^2≡105 , 628^2≡1360 , 629^2≡570 , 630^2≡1829 , 631^2≡1043 , 632^2≡259 , 633^2≡1524 , 634^2≡744 , 635^2≡2013 , 636^2≡1237 , 637^2≡463 , 638^2≡1738 , 639^2≡968 , 640^2≡200 , 641^2≡1481 , 642^2≡717 , 643^2≡2002 , 644^2≡1242 , 645^2≡484 , 646^2≡1775 , 647^2≡1021 , 648^2≡269 , 649^2≡1566 , 650^2≡818 , 651^2≡72 , 652^2≡1375 , 653^2≡633 , 654^2≡1940 , 655^2≡1202 , 656^2≡466 , 657^2≡1779 , 658^2≡1047 , 659^2≡317 , 660^2≡1636 , 661^2≡910 , |
|
[原创]整数分解随笔(五)
2047平方剩余 46^2≡69 , 47^2≡162 , 48^2≡257 , 49^2≡354 , 50^2≡453 , 51^2≡554 , 52^2≡657 , 53^2≡762 , 54^2≡869 , 55^2≡978 , 56^2≡1089 , 57^2≡1202 , 58^2≡1317 , 59^2≡1434 , 60^2≡1553 , 61^2≡1674 , 62^2≡1797 , 63^2≡1922 , 64^2≡2 , 65^2≡131 , 66^2≡262 , 67^2≡395 , 68^2≡530 , 69^2≡667 , 70^2≡806 , 71^2≡947 , 72^2≡1090 , 73^2≡1235 , 74^2≡1382 , 75^2≡1531 , 76^2≡1682 , 77^2≡1835 , 78^2≡1990 , 79^2≡100 , 80^2≡259 , 81^2≡420 , 82^2≡583 , 83^2≡748 , 84^2≡915 , 85^2≡1084 , 86^2≡1255 , 87^2≡1428 , 88^2≡1603 , 89^2≡1780 , 90^2≡1959 , 91^2≡93 , 92^2≡276 , 93^2≡461 , 94^2≡648 , 95^2≡837 , 96^2≡1028 , 97^2≡1221 , 98^2≡1416 , 99^2≡1613 , 100^2≡1812 , 101^2≡2013 , 102^2≡169 , 103^2≡374 , 104^2≡581 , 105^2≡790 , 106^2≡1001 , 107^2≡1214 , 108^2≡1429 , 109^2≡1646 , 110^2≡1865 , 111^2≡39 , 112^2≡262 , 113^2≡487 , 114^2≡714 , 115^2≡943 , 116^2≡1174 , 117^2≡1407 , 118^2≡1642 , 119^2≡1879 , 120^2≡71 , 121^2≡312 , 122^2≡555 , 123^2≡800 , 124^2≡1047 , 125^2≡1296 , 126^2≡1547 , 127^2≡1800 , 128^2≡8 , 129^2≡265 , 130^2≡524 , 131^2≡785 , 132^2≡1048 , 133^2≡1313 , 134^2≡1580 , 135^2≡1849 , 136^2≡73 , 137^2≡346 , 138^2≡621 , 139^2≡898 , 140^2≡1177 , 141^2≡1458 , 142^2≡1741 , 143^2≡2026 , 144^2≡266 , 145^2≡555 , 146^2≡846 , 147^2≡1139 , 148^2≡1434 , 149^2≡1731 , 150^2≡2030 , 151^2≡284 , 152^2≡587 , 153^2≡892 , 154^2≡1199 , 155^2≡1508 , 156^2≡1819 , 157^2≡85 , 158^2≡400 , 159^2≡717 , 160^2≡1036 , 161^2≡1357 , 162^2≡1680 , 163^2≡2005 , 164^2≡285 , 165^2≡614 , 166^2≡945 , 167^2≡1278 , 168^2≡1613 , 169^2≡1950 , 170^2≡242 , 171^2≡583 , 172^2≡926 , 173^2≡1271 , 174^2≡1618 , 175^2≡1967 , 176^2≡271 , 177^2≡624 , 178^2≡979 , 179^2≡1336 , 180^2≡1695 , 181^2≡9 , 182^2≡372 , 183^2≡737 , 184^2≡1104 , 185^2≡1473 , 186^2≡1844 , 187^2≡170 , 188^2≡545 , 189^2≡922 , 190^2≡1301 , 191^2≡1682 , 192^2≡18 , 193^2≡403 , 194^2≡790 , 195^2≡1179 , 196^2≡1570 , 197^2≡1963 , 198^2≡311 , 199^2≡708 , 200^2≡1107 , 201^2≡1508 , 202^2≡1911 , 203^2≡269 , 204^2≡676 , 205^2≡1085 , 206^2≡1496 , 207^2≡1909 , 208^2≡277 , 209^2≡694 , 210^2≡1113 , 211^2≡1534 , 212^2≡1957 , 213^2≡335 , 214^2≡762 , 215^2≡1191 , 216^2≡1622 , 217^2≡8 , 218^2≡443 , 219^2≡880 , 220^2≡1319 , 221^2≡1760 , 222^2≡156 , 223^2≡601 , 224^2≡1048 , 225^2≡1497 , 226^2≡1948 , 227^2≡354 , 228^2≡809 , 229^2≡1266 , 230^2≡1725 , 231^2≡139 , 232^2≡602 , 233^2≡1067 , 234^2≡1534 , 235^2≡2003 , 236^2≡427 , 237^2≡900 , 238^2≡1375 , 239^2≡1852 , 240^2≡284 , 241^2≡765 , 242^2≡1248 , 243^2≡1733 , 244^2≡173 , 245^2≡662 , 246^2≡1153 , 247^2≡1646 , 248^2≡94 , 249^2≡591 , 250^2≡1090 , 251^2≡1591 , 252^2≡47 , 253^2≡552 , 254^2≡1059 , 255^2≡1568 , 256^2≡32 , 257^2≡545 , 258^2≡1060 , 259^2≡1577 , 260^2≡49 , 261^2≡570 , 262^2≡1093 , 263^2≡1618 , 264^2≡98 , 265^2≡627 , 266^2≡1158 , 267^2≡1691 , 268^2≡179 , 269^2≡716 , 270^2≡1255 , 271^2≡1796 , 272^2≡292 , 273^2≡837 , 274^2≡1384 , 275^2≡1933 , 276^2≡437 , 277^2≡990 , 278^2≡1545 , 279^2≡55 , 280^2≡614 , 281^2≡1175 , 282^2≡1738 , 283^2≡256 , 284^2≡823 , 285^2≡1392 , 286^2≡1963 , 287^2≡489 , 288^2≡1064 , 289^2≡1641 , 290^2≡173 , 291^2≡754 , 292^2≡1337 , 293^2≡1922 , 294^2≡462 , 295^2≡1051 , 296^2≡1642 , 297^2≡188 , 298^2≡783 , 299^2≡1380 , 300^2≡1979 , 301^2≡533 , 302^2≡1136 , 303^2≡1741 , 304^2≡301 , 305^2≡910 , 306^2≡1521 , 307^2≡87 , 308^2≡702 , 309^2≡1319 , 310^2≡1938 , 311^2≡512 , 312^2≡1135 , 313^2≡1760 , 314^2≡340 , 315^2≡969 , 316^2≡1600 , 317^2≡186 , 318^2≡821 , 319^2≡1458 , 320^2≡50 , 321^2≡691 , 322^2≡1334 , 323^2≡1979 , 324^2≡579 , 325^2≡1228 , 326^2≡1879 , 327^2≡485 , 328^2≡1140 , 329^2≡1797 , 330^2≡409 , 331^2≡1070 , 332^2≡1733 , 333^2≡351 , 334^2≡1018 , 335^2≡1687 , 336^2≡311 , 337^2≡984 , 338^2≡1659 , 339^2≡289 , 340^2≡968 , 341^2≡1649 , 342^2≡285 , 343^2≡970 , 344^2≡1657 , 345^2≡299 , 346^2≡990 , 347^2≡1683 , 348^2≡331 , 349^2≡1028 , 350^2≡1727 , 351^2≡381 , 352^2≡1084 , 353^2≡1789 , 354^2≡449 , 355^2≡1158 , 356^2≡1869 , 357^2≡535 , |
|
[原创]整数分解随笔(五)
511平方剩余 23^2≡18 , 24^2≡65 , 25^2≡114 , 26^2≡165 , 27^2≡218 , 28^2≡273 , 29^2≡330 , 30^2≡389 , 31^2≡450 , 32^2≡2 , 33^2≡67 , 34^2≡134 , 35^2≡203 , 36^2≡274 , 37^2≡347 , 38^2≡422 , 39^2≡499 , 40^2≡67 , 41^2≡148 , 42^2≡231 , 43^2≡316 , 44^2≡403 , 45^2≡492 , 46^2≡72 , 47^2≡165 , 48^2≡260 , 49^2≡357 , 50^2≡456 , 51^2≡46 , 52^2≡149 , 53^2≡254 , 54^2≡361 , 55^2≡470 , 56^2≡70 , 57^2≡183 , 58^2≡298 , 59^2≡415 , 60^2≡23 , 61^2≡144 , 62^2≡267 , 63^2≡392 , 64^2≡8 , 65^2≡137 , 66^2≡268 , 67^2≡401 , 68^2≡25 , 69^2≡162 , 70^2≡301 , 71^2≡442 , 72^2≡74 , 73^2≡219 , 74^2≡366 , 75^2≡4 , 76^2≡155 , 77^2≡308 , 78^2≡463 , 79^2≡109 , 80^2≡268 , 81^2≡429 , 82^2≡81 , 83^2≡246 , 84^2≡413 , 85^2≡71 , 86^2≡242 , 87^2≡415 , 88^2≡79 , 89^2≡256 , 90^2≡435 , 91^2≡105 , 92^2≡288 , 93^2≡473 , 94^2≡149 , 95^2≡338 , 96^2≡18 , 97^2≡211 , 98^2≡406 , 99^2≡92 , 100^2≡291 , 101^2≡492 , 102^2≡184 , 103^2≡389 , 104^2≡85 , 105^2≡294 , 106^2≡505 , 107^2≡207 , 108^2≡422 , 109^2≡128 , 110^2≡347 , 111^2≡57 , 112^2≡280 , 113^2≡505 , 114^2≡221 , 115^2≡450 , 116^2≡170 , 117^2≡403 , 118^2≡127 , 119^2≡364 , 120^2≡92 , 121^2≡333 , 122^2≡65 , 123^2≡310 , 124^2≡46 , 125^2≡295 , 126^2≡35 , 127^2≡288 , 128^2≡32 , 129^2≡289 , 130^2≡37 , 131^2≡298 , 132^2≡50 , 133^2≡315 , 134^2≡71 , 135^2≡340 , 136^2≡100 , 137^2≡373 , 138^2≡137 , 139^2≡414 , 140^2≡182 , 141^2≡463 , 142^2≡235 , 143^2≡9 , 144^2≡296 , 145^2≡74 , 146^2≡365 , 147^2≡147 , 148^2≡442 , 149^2≡228 , 150^2≡16 , 151^2≡317 , 152^2≡109 , 153^2≡414 , 154^2≡210 , 155^2≡8 , 156^2≡319 , 157^2≡121 , 158^2≡436 , 159^2≡242 , 160^2≡50 , 161^2≡371 , 162^2≡183 , 163^2≡508 , 164^2≡324 , 165^2≡142 , 166^2≡473 , 167^2≡295 , 168^2≡119 , 169^2≡456 , 170^2≡284 , 171^2≡114 , 172^2≡457 , 173^2≡291 , 174^2≡127 , 175^2≡476 , 176^2≡316 , 177^2≡158 , 178^2≡2 , 179^2≡359 , 180^2≡207 , 181^2≡57 , 182^2≡420 , 183^2≡274 , 184^2≡130 , 185^2≡499 , 186^2≡359 , 187^2≡221 , 188^2≡85 , 189^2≡462 , 190^2≡330 , 191^2≡200 , 192^2≡72 , 193^2≡457 , 194^2≡333 , 195^2≡211 , 196^2≡91 , 197^2≡484 , 198^2≡368 , 199^2≡254 , 200^2≡142 , 201^2≡32 , 202^2≡435 , 203^2≡329 , 204^2≡225 , 205^2≡123 , 206^2≡23 , 207^2≡436 , 208^2≡340 , 209^2≡246 , 210^2≡154 , 211^2≡64 , 212^2≡487 , 213^2≡401 , 214^2≡317 , 215^2≡235 , 216^2≡155 , 217^2≡77 , 218^2≡1 , 219^2≡438 , 220^2≡366 , 221^2≡296 , 222^2≡228 , 223^2≡162 , 224^2≡98 , 225^2≡36 , 226^2≡487 , 227^2≡429 , 228^2≡373 , 229^2≡319 , 230^2≡267 , 231^2≡217 , 232^2≡169 , 233^2≡123 , 234^2≡79 , 235^2≡37 , 236^2≡508 , 237^2≡470 , 238^2≡434 , 239^2≡400 , 240^2≡368 , 241^2≡338 , 242^2≡310 , 243^2≡284 , 244^2≡260 , 245^2≡238 , 246^2≡218 , 247^2≡200 , 248^2≡184 , 249^2≡170 , 250^2≡158 , 251^2≡148 , 252^2≡140 , 253^2≡134 , 254^2≡130 , 255^2≡128 |
|
[原创]整数分解随笔(五)
④再看看平方剩余中的其它数据 现在来看这个数:2^((j-3)/2)=2^4=16 与16相邻的两个数为15、17 16*15=240 16*17=272 以逆序序列计算可得以下两个平方剩余: 1007^2≡784 , 1008^2≡752 而752=16*47 784=16*49 即k+2^((j-3)/2)*(2^((j-3)/2)-1)=2^((j-3)/2)*(3*2^((j-3)/2)-1) k+2^((j-3)/2)*(2^((j-3)/2)+1)=2^((j-3)/2)*(3*2^((j-3)/2)+1) 证明略 也即如下的三个平方剩余: 47^2≡162 , 48^2≡257 , 49^2≡354 根据公式3知:48=3*16与逆序中的((n-1)/2)-1相关的,其中平方剰余257=2^(j-3)+(1*2)/2=2^8+1=256+1 2^((j-3)/2)-1与2^((j-3)/2)+1,即47与49必是平方剩余,因49是完全平方数,2047被分解。 1007^2≡784 (mod 2047) => 1007^2≡16*49 (mod 2047) 1008^2≡752 (mod 2047) => 1008^2≡16*47 (mod 2047) 1009^2≡722 (mod 2047) => 1009^2≡2*361 (mod 2047) => 1009^2≡2*19^2 (mod 2047) 32-19=13,64*13=832 ∴831^2≡1009^2 (mod 2047) 再列出一组数据: 56^2≡1089,64^2≡2,72^2≡1090 124^2≡1047,128^2≡8,132^2≡1048 254^2≡1059,256^2≡32,258^2≡1060 511^2≡1152,512^2≡128,513^2≡1153 其中1090-1089=1 64-8=56 64+8=72 1048-1047=1 128-4=124 128+4=132 1060-1059=1 256-2=254 256+2=258 1153-1152=1 512-1=511 512+1=513 2^((11-5)/2)=2^3=8 对于这类整数是否还有其它规律,以及如何能找到一个比较适合的分解方法,目前还在找寻中,也更希望大家能给出意见及建议,本人十分感谢! |
|
[原创]整数分解随笔(五)
例2 2047=2^11-1(见后面所附平方剩余) ① 这里n=2047, j=11 k=2^(11-2)=2^9=512 ((n-1)/2)^2≡((2047-1)/2)^2≡1023^2≡512 (mod 2047)(请参考随笔1) (11+1)/2=6,2^6=64 64^2≡2 (mod 2047) 公式1 (11-1)/2=5, 2^5=32 (11-3)/2=4, 2^4=16 2^((j-1)/2)=2^((11-1)/2)=2^5=32 2^((j-3)/2)=2^((11-3)/2)=2^4=16 ② 由公式2得到如下的平方剩余: 当h=1 (64*1)^2≡2*1 (mod 2047) 第1个公式左边: (1*64-1)^2=63^2 第1个公式右边:2*(32-1)^2=2*31^2=2*961=1922 (mod 2047) 即 63^2≡1922 (mod 2047) 第2个公式左边: (1*64+1)^2=65^2 第2个公式右边:2*(32+1)^2=2*33^2=2*1089=2178≡131 (mod 2047) 即 65^2≡131 (mod 2047) 把这三个数整理得: 63^2≡1922 , 64^2≡2 , 65^2≡131 当然根据上面三式观察可得: 63^2≡1922=2*31^2 (mod 2047) 65^2≡131 (mod 2047) => 65^2≡131+2047 (mod 2047) => 65^2≡2178 (mod 2047) => 65^2≡2*1089 (mod 2047) => 65^2≡2*33^2 (mod 2047) 其中31+33=64 当h=2 (64*2)^2≡2*4 (mod 2047) (2*64-1)^2=127^2≡2*(32-2)^2=2*30^2=2*900=1800 (mod 2047) (2*64+1)^2=129^2≡2*(32+2)^2=2*34^2=2*1156=2312≡265 (mod 2047) 其中 30+34=64 当h=3 (64*3)^2≡2*9 (mod 2047) (3*64-1)^2=191^2≡2*(32-3)^2=2*29^2=2*841=1682 (mod 2047) (3*64+1)^2=193^2≡2*(32+3)^2=2*35^2=2*1225=2450≡403 (mod 2047) 其中 29+35=64 . . . 请看以下所附数据: 63^2≡1922 , 64^2≡2 , 65^2≡131 127^2≡1800 , 128^2≡8 , 129^2≡265 191^2≡1682 , 192^2≡18 , 193^2≡403 255^2≡1568 , 256^2≡32 , 257^2≡545 319^2≡1458 , 320^2≡50 , 321^2≡691 383^2≡1352 , 384^2≡72 , 385^2≡841 447^2≡1250 , 448^2≡98 , 449^2≡995 511^2≡1152 , 512^2≡128 , 513^2≡1153 575^2≡1058 , 576^2≡162 , 577^2≡1315 639^2≡968 , 640^2≡200 , 641^2≡1481 703^2≡882 , 704^2≡242 , 705^2≡1651 767^2≡800 , 768^2≡288 , 769^2≡1825 831^2≡722 , 832^2≡338 , 833^2≡2003 895^2≡648 , 896^2≡392 , 897^2≡138 959^2≡578 , 960^2≡450 , 961^2≡324 1023^2≡512 , 1024^2≡512 , 1025^2≡514 这里385^2≡841 (mod 2047) 而841+2047=2888=2*1444=2*38^2 又因841*2=29^2*2≡1684,32-29=3 ∴64*3-1=191,即191^2≡385^2 (mod 2047) 再列举一组数据: 63^2≡1922=2*31^2,64^2≡2,65^2≡131≡2178=2*33^2 127^2≡1800=8*15^2,128^2≡8,129^2≡265≡2312=8*17^2 255^2≡1568=32*7^2,256^2≡32,257^2≡545≡2592=32*9^2 511^2≡1152=128*3^2,512^2≡128,513^2≡1153≡3200=128*5^2 ③现在看公式3: 当t=1,s=1 (1*64+1)^2≡65^2≡131 (mod 2047) 则 2*(1+32*1)^2≡131 (mod 2047) 当t=2,s=1 (2*64+1)^2≡129^2≡265 (mod 2047) 则 2*(2+32*1)^2=2*34^2≡265 (mod 2047) 当t=3,s=4 (3*64+4)^2≡196^2≡1570 (mod 2047) 则 2*(3+32*4)^2=2*131^2≡1570 (mod 2047) 当t=6,s=13 (6*64+13)^2≡397^2≡2037 (mod 2047) 则 2*(6+32*13)^2=2*422^2≡2073 (mod 2047) . . . |
|
[原创]整数分解随笔(五)
③现在看公式3: 当t=1,s=1 (1*32+1)^2≡33^2≡67 (mod 511) 则 2*(1+16*1)^2≡67 (mod 511) 当t=2,s=1 (2*32+1)^2≡65^2≡137 (mod 511) 则 2*(2+16*1)^2=2*18^2≡137 (mod 511) 当t=3,s=4 (3*32+4)^2≡100^2≡291 (mod 511) 则 2*(3+16*4)^2=2*67^2≡291 (mod 511) 当t=6,s=13 (6*32+13)^2≡205^2≡123 (mod 511) 则 2*(6+16*13)^2=2*214^2≡317 (mod 511) . . . ④再看看平方剩余中的其它数据 设n=2^j-1,j=2m+1,m>=1,则(3*2^((j-3)/2)^2≡2^(j-3)+1 (mod n) 证明: ∵ n=2^j-1 => 2^j≡1 (mod n) => 2^(j-3+3)≡1(mod n) => 2^3*(2^((j-3)/2))^2≡1 (mod n) => 9*(2^((j-3)/2))^2-(2^((j-3)/2))^2≡1 (mod n) => (3*2^((j-3)/2)^2≡2^(j-3)+1 (mod n) 证毕 更一般的公式为: 如果n=2^j-1,j=2m+1,m,t>=1,则 ((2t+1)*2^((j-3)/2))^2≡2^(j-3)+t(t+1)/2 (mod n) (证明略) 当j=9,则(3*2^3)^2=24^2≡2^6+1=65 (mod 511) 对于3*8=24,前后两个值23和25也是平方剩余(证明略),具体说明见2047,这里只例举出一些对应关系。 23^2≡18 (mod 511)和25^2≡114 (mod 511),这两个数3*2^((j-3)/2)-1、3*2^((j-3)/2)+l的平方剩余能被6整除(证明略)。 248^2≡8*23=184=8*7+128 (mod 511) 247^2≡8*25=200=8*9+128 (mod 511) (248*32)^2=240^2≡184*2=368 (mod 511) (247*32)^2=239^2≡200*2=400 (mod 511) (254/32)^2=24^2≡130/2=65 (mod 511) {253/32)^2=40^2≡134/2=67 (mod 511) (252/32)^2=56^2≡140/2=70 (mod 511) . . . 这里254^2≡130 (mod 511), 130*2=260 260-128=132=11*12,即260在逆序序列中,254*32≡48 (mod 511) 又因为 32^2≡2 (mod 511),所以 48^2≡244^2 (mod 511) 还有247^2≡200 (mod 511) ∵200=2*100=2*10^2 又∵ 16-10=6,∴32*6=192(见②) 即 247^2≡191^2 (mod 511) 再列出一组数据: 28^2≡273,32^2≡2,36^2≡274 62^2≡267,64^2≡8,66^2≡268 127^2≡288,128^2≡32,129^2≡289 其中274-273=1 32-4=28 32+4=36 268-267=1 64-2=62 64+2=66 289-288=1 128-127=1 128+1=129 2^((j-5)/2)=2^2=4 该关系式的证明主要依据d-c≡4ai(见随笔2),因为n=2^j-1都是4k-1型,4k≡1 (mod n)即可得到上述的关系式,这里具体证明略。 现在要找寻是否存在像23与25这种类型的平方剩余(因为25是个完全平方数),如79^2≡219,80^2≡268,81^2≡429,79与81也是平方剩余,而253*32≡80 (mod 511),119^2≡364,120^2≡92,121^2≡333,120=8*15(2^((j-3)/2),当j=9时为8),119和121也是平方剩余,这种平方剩余该去如何计算?是否会存在某种关系?当然只是一种猜测,也许本身就不存在。 |