3

我对 Perl 非常陌生，所以我希望你能原谅我的缺乏经验。

我有以下代码行：

use warnings;
use strict;
use POSIX 'ceil';
use bigint;


my($g, $y, $n) = ($ARGV[0], $ARGV[1], $ARGV[2]);

my $z = ceil(sqrt($n-1));

my $entry;

print "list1: \n";
for my $v (0 .. $z) {
    $entry = ($g ** $v) % $n;
    $entry = ($entry ** ($n - 2)) % $n;
    $entry = ($entry * $y) % $n;

    print "$entry : $v\n";
}

print "list2: \n";
for my $u (0 .. $z) {
    $entry = ($g ** ($u * $z)) % $n;
    print "$entry: $u\n";
}

由于以下一些陈述，我需要使用 bigint 环境。每当我查看$z它时，当我使用$n = 41. 看起来好像 bigint 环境对sqrt方法的值进行了四舍五入。我也尝试使用 BigFloat 而不是 bigint，但是结果$entry = ($g ** ($u * $z)) % $n;计算错误（($g, $y, $n) = (15, 38, 41)结果是 3，当$u在 for 循环中达到 3，但应该是 26）。

是否有任何选项可以避免这种舍入，所以我可以在以下所有语句中计算平方根和 bigint 时使用浮点数，以便 pow 操作正常工作？

我的电话是perl program.pl 15 38 41。我尝试实现baby-step-giant-step 算法。

4

3 回答 3

4

你需要使用bignum，而不是bigint：

$ cat bauer.pl 
#!/usr/bin/perl
use warnings;
use strict;
use POSIX;
use bigint;


my($g, $y, $n) = ($ARGV[0], $ARGV[1], $ARGV[2]);

my $z = ceil(sqrt($n-1));

$ perl r.pl 
1.41421356237309504880168872420969807857

使用您的程序签名：

$ cat bauer.pl 
#!/usr/bin/perl

use warnings;
use strict;
use POSIX;
use bignum;


my($g, $y, $n) = ($ARGV[0], $ARGV[1], $ARGV[2]);

my $z = ceil(sqrt($n-1));
print STDOUT "$z\n";

$ perl bauer.pl 1 2 48
7
于 2019-12-12T23:18:11.873 回答
3

我会推荐Math::BigFloat和Math::BigInt而不是bigint pragma，几乎总是如此。

编译指示“只是 Math::BigInt 系列的各种模块的一个薄包装”，（链接的）文档说，但具有非常重要的动作（“描述”传达了它）。取而代之的是，使用类来设置您想要的无限精度支持，这本身并不简单且成本高昂。

use warnings;
use strict;
use feature 'say';

use Math::BigFloat;

my($g, $y, $n) = ($ARGV[0], $ARGV[1], $ARGV[2]);

my $z = sqrt($n-1);
say $z; 

my $num = Math::BigFloat->new( $z );
say $num;

my $num_ceil = $num->bceil();
say $num_ceil;

更新   显示的计算不需要大数指数

use warnings;
use strict;
use feature 'say';

use POSIX 'ceil';
use Math::BigInt;

my ($g, $y, $n) = @ARGV;

my $z = ceil(sqrt($n-1));

my $bg = Math::BigInt->new($g);

my $e;
for my $u (0 .. $z) {
    $e = $bg->copy->bmodpow($u*$rnd, $n);
    say "$u:  $e";
}

碰巧有一种bmodpow方法，它完全按照需要做并且在这方面“远远优于”。大多数算术方法都会修改它们的操作数，因此copy()被链接起来以保留$bg下一次迭代。请参阅文档中的警告下的“修改和 = ”项目符号。

我$e在循环外部声明以避免每次在循环中运行（复制）构造函数，因为变量成为（被分配）一个BigInt由方法返回的对象。（我不确定这是否需要或它是否有帮助。）

于 2019-12-13T00:15:24.770 回答
2

每当我查看 $z 时，它的计算结果为 6 而不是 7，

use bigint;导致数字文字被 Math::BigInt 对象替换。例如，

1

被替换为

Math::BigInt->new(1)

当将 Math::BigInt 对象用作操作数时，Math::BigInt 又会覆盖许多运算符。

像这样，

use bigint;
my $z = ceil(sqrt($n-1));

相当于

use Math::BigInt;
my $z = ceil(sqrt($n-Math::BigInt->new(1)));

这相当于

use Math::BigInt;

my $temp = Math::BigInt->new(1);   #  1 [BigInt]
$temp->bneg;                       # -1 [BigInt]
$temp->badd($n);                   # 40 [BigInt]
$temp->bsqrt();                    #  6 [BigInt]      <--- XXX
$temp = $temp->numify;             #  6 [Primitive]
my $z = ceil($temp);               #  6 [Primitive]

因此，当您不想使用时，您正在使用 Math::BigInt。不要那样做！！！只需使用

# No "use bigint;"!!!
my $z = ceil(sqrt($n-1));

当然，您链接的算法实际上需要

# No "use bigint;"!!!
my $z = ceil(sqrt($n));

因为use bigint;可以在远处产生很大的影响，我个人觉得use bigint;太神奇了。我宁愿Math::BigInt->new(...)在适当的地方使用，也不愿use bigint;将所有数值常量转换为 Math::BigInt 对象。我也宁愿使用 Math::BigInt 的方法而不是重载的运算符。这样的惊喜要少得多（例如，使用 时失去大量支持ceil）。

use warnings;
use strict;
use feature qw( say );

use Config       qw( %Config );
use Math::BigInt qw( );
use POSIX        qw( ceil );

# Each of the arguments is expected to be in [0, 2^32).
# Should use exponentiation by squaring instead of larger number support.
sub pow_m {
   my ($base, $exp, $mod) = @_;
   my $n = Math::BigInt->new($base);
   $n->bpow($exp);
   $n->bmod($mod);
   return $n->numify();
}

# Each of the arguments is expected to be in [0, 2^32).
# Requires a 64-bit integers or $e might overflow.
sub babystep_giantstep {
   my ($g, $h, $mod) = @_;

   my $m = ceil(sqrt($mod));

   my %table;

   my $e = 1;
   for my $i (0..$m-1) {
      $table{$e} = $i;
      $e = ($e * $g) % $mod;
   }

   my $factor = pow_m($g, $mod-$m-1, $mod);

   $e = $h;
   for my $i (0..$m-1) {
      if (exists($table{$e})) {
         return $i*$m + $table{$e};
      }

      $e = ($e * $factor) % $mod;
   }

   return undef;
}

{
   $Config{uvsize} >= 8
      or warn("Results may overflow\n");

   my ($g, $h, $mod) = @ARGV;   
   my $log = babystep_giantstep($g, $h, $mod);
   say $log;

   my $test = Math::BigInt->new($g);
   $test->bpow($log);
   $test->bmod($mod);
   $test = $test->numify;
   say $test == $h ? "ok" : "not ok";
}
于 2019-12-13T06:12:38.980 回答