Haskell中相同值表达式运算结果不一致问题求助

你的问题核心是整数类型溢出，以及Haskell类型推断规则导致两种写法的计算路径完全不同：

1. 当使用mod (v1*v2)时，Haskell会默认将输入参数31和11推断为Int类型（32位整数，最大值约20亿），因此v1*v2的结果也是Int。而product (replicate 43 x)的结果是极大数（比如235^43），远超出Int的取值范围，会发生溢出截断，最终mod计算使用的是溢出后的错误数值，得到非预期结果。

2. 当直接使用mod 341时，Haskell会自动将类型提升为任意精度的Integer（因为product的结果默认是Integer，mod要求左右操作数类型一致），所有计算都在无溢出的任意精度整数环境下进行，结果自然正确。

验证与修复方案 #

验证类型差异 #

在GHCi中可以直观看到类型区别：

:type 31*11  -- 未指定类型时，默认输出 Int
:type 341    -- 与Integer类型值运算时，会被自动提升为 Integer

修复方法 #

有两种可靠的修复方式：

• 显式指定函数参数类型为Integer，强制所有计算使用任意精度整数：

  prub :: Integer -> Integer -> Integer -> [Integer] -> [Integer]
  prub v1 v2 e l = map (`mod` (v1*v2)) (map product (map (replicate (exp1 ((v1-1)*(v2-1)) e)) l))
  

• 显式将v1*v2转换为Integer：

  prub v1 v2 e l = map (`mod` (toInteger (v1*v2))) (map product (map (replicate (exp1 ((v1-1)*(v2-1)) e)) l))
  

额外建议 #

在RSA实现中，所有大数运算都应该使用Integer类型避免溢出。另外你的exp1函数通过遍历列表找模逆元的方式效率很低，建议使用扩展欧几里得算法直接计算模逆元，或者使用Data.Numeric.Modular库简化模运算逻辑。

内容的提问来源于stack exchange，提问作者Tomas Mansilla Panozzo