#としじのPS その10～発展問題２：冪剰余 c:=b^e mod m～

#としじのPS その10～発展問題２～

早くも趣味に走ってますね、さっすが俺ｗ
大きな数から余りを求めようとすると、PSは見当違いの数を返してくるようです。ここはエラーでも吐いてほしかったな、まあいいや。

例えば46の46乗を47で割ったときの余りを求めたいとします。
この答えは1になるのですが、僕の環境ではPSは5を返してきました。

$a = [math]::Pow(46,46)
$a % 47

細かいことはちょっとわからないのですが、ケタ落ちしてるんでしょうね。Twitterでそれを回避するアルゴリズムを教わったので試してみました！

cls; cd C:\PowerShell

# aのn乗をmで割った余りを返却
function LargeMod($a,$n,$m){
   $ret=$a%$m
   if($n-ge 2){
       2..$n|%{$ret=($ret*$a)%$m}
   }
   $ret
}

(LargeMod  46 46 47)
(LargeMod  28 28 47)
(LargeMod  30 30 47)
(LargeMod  37 37 47)
(LargeMod  31 31 47)
(LargeMod  40 40 47)
(LargeMod  18 18 47)
(LargeMod -11 11 47) +47
(LargeMod -41 41 47) +47
-(LargeMod -42 42 47) +47
(LargeMod  43 43 47)
(LargeMod  27 27 47)

美しいですね！

買っちまった😆✨ pic.twitter.com/A6yuMXWfDK

— としじ🎤VBAer (@toshi81350036) September 5, 2021

ついでにVBAでも書いてみました♪

' aのn乗をmで割った余りを返却 '
Function LargeMod(a, n, m): Dim i, ret
  ret = a Mod m
  If n >= 2 Then
     For i = 2 To n
        ret = (ret * a) Mod m
     Next
  End If
  LargeMod = ret
End Function

Sub Main()
  Debug.Print (LargeMod(46, 46, 47))
  Debug.Print (LargeMod(28, 28, 47))
  Debug.Print (LargeMod(30, 30, 47))
  Debug.Print (LargeMod(37, 37, 47))
  Debug.Print (LargeMod(31, 31, 47))
  Debug.Print (LargeMod(40, 40, 47))
  Debug.Print (LargeMod(18, 18, 47))
  Debug.Print (LargeMod(-11, 11, 47) + 47)
  Debug.Print (LargeMod(-41, 41, 47) + 47)
  Debug.Print (LargeMod(-42, 42, 47) - 47) * -1
  Debug.Print (LargeMod(43, 43, 47))
  Debug.Print (LargeMod(27, 27, 47))
End Sub

さらにPythonのPowを再現してみた、中身のロジックについては再現しているのかどうかはわからないけども←

Function Pow(b, e, Optional m): Dim i, ret
  
  If IsMissing(m) Then
     Pow = b ^ e
     Exit Function
  End If
  
  ret = b Mod m
  If e >= 2 Then
     For i = 2 To e
        ret = (ret * b) Mod m
     Next
  End If
  Pow = ret
  
End Function

あれ、PSについて語るハズでは・・・ま、いっかｗ

やっぱりよくない、PSでも書きましょうｗ

cls; cd C:\PowerShell

function Pow($b, $e, $m = 0){

   if($m -eq 0){return [math]::Pow($b, $e)}

   $ret = $b % $m
   if($e -ge 2){
       2..$e | % {$ret = ($ret * $b) % $m}
   }
   return $ret
}

Pow 46 46 
Pow 46 46 47

このデータならマイナスを考慮せずともちゃんと出るとのこと・・・
どうやってこんなの見つけてきてるんでしょうね、不思議😇