时间戳

首页 > 解决方案 > 使用费马素性检验的乘法模逆（Assembly MIPS）

math - 使用费马素性检验的乘法模逆（Assembly MIPS）

问题描述

接收两个整数a并p打印x出它ax ≡ 1 (mod p)
p是素数且a不是 p 的倍数

该代码在 MARS 中完美运行，但在 QTSpim 中它抱怨 overlfow ( immediate value 825265 out of range) 并指责错误时p和素数。为什么两者之间有这种差异？

在此处输入图像描述

    .data
message1: .asciiz "Invali Input\n"
message2: .asciiz "inverse = "
message3: .asciiz "The module is not a prime\n"
finalLine: .asciiz "\n"
    .text
main:
    li $v0, 5
    syscall
    move $t8, $v0
    
    li $v0, 5
    syscall
    move $t9, $v0
    beq $t8, 2, verifyMult
    ble $t8, 1, invalidInput
    ble $t9, 1, invalidInput
    
    j pr

verifyMult:
    div $t9, $t8
    mfhi $s1
    beq $s1, 0, invalidInput
    j modInverse
main3:  
    li $v0, 4
    la $a0, message2
    syscall
    
    li $v0, 1
    move $a0, $t4
    syscall
    
    li $v0, 4
    la $a0, finalLine
    syscall
    
    li $v0, 10
    syscall

invalidInput:
    li $v0, 4
    la $a0, message1
    syscall 
    
    li $v0, 10
    syscall
    
invalidMod:
    li $v0, 4
    la $a0, message3
    syscall 
    
    li $v0, 10
    syscall
modInverse:
    move $t0, $t8
    move $t1, $t9
    
    addi $t2, $t0, 0 
    addi $t3, $zero, 0
    addi $t4, $zero, 1
    while:
        ble $t1, 1, exit  
        div $t1, $t0
        mflo $t5
        addi $t6, $t0, 0
        mfhi $t0
        
        addi $t1, $t6, 0
        addi $t6, $t3, 0
        
        mult $t5, $t3
        mflo $s0
        
        sub $t3, $t4, $s0
        addi $t4, $t6, 0
        j while 
        
    exit:
        blt $t4, 0, makePositive
        j main3
        
    makePositive: 
        add $t4, $t4, $t2
        j main3

pr: 
      add  $s5, $t8, $zero  
      
      andi $t1,$s5,1
      beq $t1,$zero, invalidMod 
      
      xor $t0,$t0,$t0
      addiu $t0,$t0,561
      beq $s5,$t0, invalidMod 
      
      xor $t0,$t0,$t0
      addiu $t0,$t0,1105
      beq $s5,$t0, invalidMod 
      
      xor $t0,$t0,$t0
      addiu $t0,$t0,1729
      beq $s5,$t0, invalidMod 
      
      xor $t0,$t0,$t0
      addiu $t0,$t0,2465
      beq $s5,$t0, invalidMod
      
       xor $t0,$t0,$t0
      addiu $t0,$t0,2821
      beq $s5,$t0, invalidMod
      
      xor $t0,$t0,$t0
      addiu $t0,$t0,6601
      beq $s5,$t0, invalidMod 
      
      xor $t0,$t0,$t0
      addiu $t0,$t0,8911
      beq $s5,$t0, invalidMod 
      
      xor $t0,$t0,$t0
      addiu $t0,$t0,10585
      beq $s5,$t0, invalidMod
      
      addiu $t2,$t2,41041
      beq $s5,$t2, invalidMod 
      
      addiu $t3,$t3,825265
      beq $s5, $t3 , invalidMod 
      
      addiu $t4,$t4,321197185 
      beq $s5,$t4, invalidMod 
      
      move $s1,$s5
      xor $t2,$t2,$t2

      xor $t3,$t3,$t3
     
      xor $t4,$t4,$t4
      addiu $t4,$t4,2 
     
     
loop_exponent:
     andi $t1,$s5,1      
     beq $t1,$zero, even_exponent
    
     subiu $s5,$s5,1
     
     sll $t2,$t2,1   
     addiu $t2,$t2,1   

     j next_iteration   

even_exponent:
    sll $t2,$t2,1
    srl $s5,$s5,1
    
next_iteration:
     addiu $t3,$t3,1      
     bne $s5,$t4, loop_exponent      
     

     sll $t2,$t2,1
     addiu $t3,$t3,1  
    
     xor $t5,$t5,$t5
     addiu $t5,$t5,3
     
     xor $t6,$t6,$t6
     addiu $t6,$t6,3
     
loop_compute_mod:
     andi $t1,$t2,1      
     beq $t1,$zero, even
     
     multu $t5,$t6
     mflo $t5
     divu $t5,$s1

     mfhi $t5
     j next_exponent_bit
even:
    multu $t5,$t5
    mflo $t5
    divu $t5,$s1

    mfhi $t5
 
 next_exponent_bit:

    subiu $t3,$t3,1
    srl $t2,$t2,1
    bgtz $t3, loop_compute_mod     
     
     divu $t6,$s1
     mfhi $t6
     
     beq $t5,$t6,verifyMult
     j invalidMod

标签： mathassemblymipsqtspimimmediate-operand

解决方案

MARS 允许将每条指令视为伪指令，通过在另一个寄存器中构造值来处理大立即数。

QtSpim 更像是传统的 MIPS 汇编器，它只将少数指令（如li）视为伪指令，而不是addiu.

825265不适合 16 位有符号立即数。也没有41041——SPIM 也应该抱怨这一点。

推荐阅读