[数值计算] 批处理求质数与批处理RSA算法

cjiabing

      质数，又称素数，指在一个大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。
比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。
      维基百科：http://zh.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0
      素数近来被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入素数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找素数的过程（分解质因数）过久，使即使取得信息也会无意义。
      百度百科：http://baike.baidu.com/view/1767.htm

      一、用批处理找出 1000 以内的素数！~
      可以用排除法，从2开始找往上找，1000/2=500， 如果能被2整除就排除掉，如果被3整除就排除掉，……，直到剩下的都不被其他数整除。
      可以用余数来判断，有余数的可能是素数，但还要进一步分析，可我不熟悉批处理这个余数到底是怎么回事，跟理解的有出入。

1000以内质数表
　　2 3 5 7 11 13 17 19 23 29 　　31 37 41 43 47 53 59 61 67 71 　　73 79 83 89 97 101 103 107 109 113 　　127 131 137 139 149 151 157 163 167 173 　　179 181 191 193 197 199 211 223 227 229 　　233 239 241 251 257 263 269 271 277 281 　　283 293 307 311 313 317 331 337 347 349 　　353 359 367 373 379 383 389 397 401 409 　　419 421 431 433 439 443 449 457 461 463 　　467 479 487 491 499 503 509 521 523 541 　　547 557 563 569 571 577 587 593 599 601 　　607 613 617 619 631 641 643 647 653 659 　　661 673 677 683 691 701 709 719 727 733 　　739 743 751 757 761 769 773 787 797 809 　　811 821 823 827 829 839 853 857 859 863 　　877 881 883 887 907 911 919 929 937 941 　　947 953 967 971 977 983 991 997 (168个)

      二、RSA算法——请试用批处理来演示RSA算法？

RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在（美国麻省理工学院）开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
      22、21楼有演算介绍。
      素数与密码的算法：http://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95
      详细：http://blog.csdn.net/fireseed/article/details/327444
      百度百科：http://baike.baidu.com/view/7520.htm

QIAOXINGXING

@echo off&setlocal enabledelayedexpansion&cd /d "%~dp0"
set "n=0"
for /l %%i in (2 1 1000) do (
  set "a=%%i"
  set /a "b=a/2+1"
  if !b! gtr 32  set /a "b=32"
  call :1
  if  "!c!"=="!b!"  set /a "n+=1"&echo !n!:!a!
)
pause
:1
  for /l %%a in (2 1 !b!) do (
    set "c=%%a"
    set /a "d=a%%c"
    if "!d!"=="0" goto :eof
  )
复制代码

find

http://www.bathome.net/thread-53-1-1.html
http://www.bathome.net/thread-2372-1-1.html
http://www.bathome.net/thread-11449-1-1.html
http://www.bathome.net/thread-3635-1-1.html

ivor

说实话我还不知道怎么利用素数用与密码

Demon

Input: an integer n > 1
 
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
 
for i = 2, 3, 4, ..., while i ≤ n/2:
  if A[i] is true:
    for j = 2i, 3i, 4i, ..., while j ≤ n:
      A[j] = false
 
Now all i such that A[i] is true are prime.
复制代码

cjiabing

回复 4# ivor


    谢谢大家！~我正在弄，把普通字符翻译成素数，然后将素数的解因子做成密钥，就可以成为密码了！~
    想了一个晚上哦。

applba

@echo off
SETLOCAL EnablEdElayEdExpansion

for /l  %%a in (3,1,100) do (
    set /a flag=1
    set /a  n=%%a-1
    for /l %%A in (2,1,!n!) do (
        set /a r=%%a %% %%A
        if !r! equ 0 ( set /a flag=0 )
    )
    if !flag! equ 1  set "s=!s! %%a"
)
echo %s%
pause
复制代码

cjiabing

RSA算法，要进行幂运算，数学盲，还是等plp626来解决算了！~

find

回复 8# cjiabing


初中数学课本上就已经有幂运算了吧

jinzeyu

@echo off&setlocal enabledelayedexpansion&echo 2 是质数&(for /l %%a in (3,2,1000) do call:1 %%a)&echo 计算完成&pause>nul&exit
:1
set a=32&if %1 lss 32 set /a a=%1-1
for /l %%b in (3,2,!a!) do (
  set /a i=%1%%%%b
  if "!i!"=="0" (set $%1=.&goto 2)
)
:2
if not defined $%1 echo %1 是质数
复制代码

RuiIsRui

11 以下的5个数不在............我是写来算6位质数的，改给你用了

@echo off&setlocal Enabledelayedexpansion
set/a MinShu=10
set/a MaxShu=1000
set/a N=0
for /l %%i in (%MinShu%,1,%MaxShu%) do (
set/a JShu=%%i
call:AA
)
echo %MinShu% ~ %MaxShu% 有 %N% 个质数
pause
exit
:AA

for %%i in (2,3,5,7,11) do (
set/a b=%JShu%%%%%i
if "!b!"=="0" GOTO:eof
)

set/a MinShu2=%JShu%/10
for /l %%i in (12,1,%MinShu2%) do (
set/a d=%JShu%%%%%i
if "!d!"=="0" GOTO:eof
)
echo 质数%N%.素数:%JShu%
set/a N+=1
GOTO:eof
复制代码

cjiabing

回复 9# find

    谢谢您的链接！我的都忘记搜索了。
    有跟学跟学会跟还记得的关系可没有多大的关联了，特别是用批处理来表达幂，这种体力活还是留给专业的plp626合适！~

cjiabing

回复 7# applba


    结果是

 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57
59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99
复制代码

     9能被3除不属于素数。

cjiabing

回复 10# jinzeyu


    后面的应该对，但开头被你漏掉好多个了：

 
2 是质数
37 是质数
41 是质数
43 是质数
47 是质数
复制代码

cjiabing

回复 11# RuiIsRui


    你的没有看见前面几个呢

质数0.素数:13
质数1.素数:17
质数2.素数:19
质数3.素数:23
质数4.素数:29
质数5.素数:31
质数6.素数:37
复制代码