形はa^b(mod p)=dでpが質量数の方程式の解のようです

今年はctfやってないけど、またこんな問題出たそう(?)とりあえず今まで出会ったことのあるいくつかをまとめて、自分のファイルを保存します.数学の原理は何ですか.存在しない、私はACMerではありません(この時、レンガを運ぶ民工がコードをつかむのは呼び出しです(いいえ
既知a b p,dを求める
一般的に高速べき乗と高速乗は比較的安全ですがpythonは直接pow()で、高速べき乗だけを書いてもいいです.int任意精度は良い文明(隣のc++のlong longがまた爆発したのを見て(小声でつぶやくがここに問題があるのはpow()の計算精度・・・何が起こっているのかよく分からないorz具体的な体現は安恒2018年7月試合-Crypto-dangerous rsaという問題を見ることができ、最後まで解決できず、ひざまずいた()

def mul(a,b,p):
  r=0
  t=a
  while(b):
    if(b&1):
      r=(r+t)%p
    t=(t<<1)%p
    b>>=1
  return r

def fast_pow(a,b,p):
    r=1
    t=a
    while(b):
        if(b&1):
          r=mul(r,t,p)%p
        t=mul(t,t,p)%p
        b>>=1
    return r

print(fast_pow(2,3,5))

余談ですが、高速べき乗には2つの実装方法(再帰とループ)があります.ここではループを使用します.https://www.cnblogs.com/chengd/articles/7103854.html
再帰効率が高くなく、再帰階層が多すぎるとスタックオーバーフロー(コンピュータでは、関数呼び出しはスタック(stack)というデータ構造によって実現され、1つの関数呼び出しに入るたびにスタックフレームが追加され、関数が戻るたびにスタックフレームが減少する.スタックのサイズは無限ではないため、再帰呼び出しの回数が多すぎるとスタックがオーバーフローする)
昨年RSAに高速べき乗型取り関数を書いたときに出た問題をやっと解いたx唐突爆スタックが突然防げなかった(......)つまり書くアルゴリズムを学んだときは実際の状況に基づいて時間の複雑さと空間の複雑さを比較しなければならず、通常は非再帰よりも再帰的な時間の複雑さが多く、図が上手だからといって盲目的に再帰するわけにはいかない(.自分も反省して、データ構造を学んだことがある.再帰がスタックを爆発させることを知っているはずだ.どうして自分が叩いたとき、まさか(......)この時、辛い鶏が通りかかったのか.
既知a d p、bを求める
去年のhgameの第1周の问题、テーマ名は直接ヒントで、たとえこのようにしても长い间振り回されて、ACMを游ばないのは本当に损をして、まだ耻ずかしいです()BSGSコード(元のウェブサイトはすでに挂かっています):https://pythonexample.com/snippet/bsgspy_0xtowel_python

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# Towel 2017
from math import ceil, sqrt
def bsgs(g, h, p):
    '''
    Solve for x in h = g^x mod p given a prime p.
    If p is not prime, you shouldn't use BSGS anyway.
    '''
    N = ceil(sqrt(p - 1)) # phi(p) is p-1 if p is prime
    # Store hashmap of g^{1...m} (mod p). Baby step.
    tbl = {pow(g, i, p):i for i in range(N)}
    # Precompute via Fermat's Little Theorem
    c = pow(g, N * (p - 2), p)
    # Search for an equivalence in the table. Giant step.
    for j in range(N):
        y = (h % p * pow(c, j, p)) % p
        if y in tbl:
            a = j * N + tbl[y]
            print(a)
#            return j * N + tbl[y]
    # Solution not found
    return a
#print(bsgs(73300775185, 527242847469, 650260984909))

余談*2、拡張BSGSはpが素数ではない場合に対して、この2つのアルゴリズムの具体的な原理は参考にすることができる:https://blog.csdn.net/lycheng1215/article/details/79047734c++のBSGSexコードが付属しており、非常に親切()および:https://blog.csdn.net/a27038/article/details/77341735原理から手順からコードからアプリケーションまで詳しく、同じコードが付いているので、強くお勧めします.
既知のb d p、aを求める
友达が先日私に闻いた问题で、私も直接亡くなったのを见て(・・)それからこの编を探して、ああ、大物、私は死んでしまいました(https://blog.csdn.net/acdreamers/article/details/9500215
数日後に思い出したらpython版のコードを補充します.
拡張読書&実用化

Pythonチュートリアル-再帰関数-廖雪峰

【詳細】快速べき乗&亀速乗&快速乗-Cyan_rose

FZU - 1759- Super A^B mod C

HDU - 5187 - zhx's contest

Baby-step giant-step - Wikipedia

Pohlig–Hellman algorithm - Wikipedia

POJ - 2417 - Discrete Logging

いくつかの数論概念とアルゴリズム--SGU 261から-雪琼-ブログ園

SGU - 261 - Discrete Roots

HDU - 3930 - Broot