首页 > 其他分享 >2023-12-02:用go语言,如何求模立方根? x^3=a mod p, p是大于等于3的大质数, a是1到p-1范围的整数常数, x也是1到p-1范围的整数,求x。 p过大,x不能从1到p-1遍

2023-12-02:用go语言,如何求模立方根? x^3=a mod p, p是大于等于3的大质数, a是1到p-1范围的整数常数, x也是1到p-1范围的整数,求x。 p过大,x不能从1到p-1遍

时间:2023-12-02 19:44:39浏览次数:54  
标签:12 big 质数 整数 立方根 复数 go mod

2023-12-02:用go语言,如何求模立方根?

x^3=a mod p,

p是大于等于3的大质数,

a是1到p-1范围的整数常数,

x也是1到p-1范围的整数,求x。

p过大,x不能从1到p-1遍历。

答案2023-12-02:

灵捷3.5

大体步骤如下:

1.判断是否存在模立方根。有0,1,3个根这三种情况。

1.1.求p-1和3的最大公约数gcd(p-1,3)。最后结果要么是1,要么是3。如果是1,那肯定模立方根,但只有1个根。如果是3,进行下一步。

1.2.欧拉判别法。a**[(p-1)/3]==1 mod p。如果等于1,那就有3个根。如果不等于1,那就是0个根。

2.Peralta算法。求y。

2.1.当只有0个根时,直接返回。

2.2.当只有1个根时,a ^ ((p-1)/3) mod p就是答案。

2.3.当有3个根时,这个很难描述,具体见代码。

2.3.1.定义复数乘法和复数的快速幂。这虽然叫复数,但跟传统意义上的复数是不一样的。

2.3.2.确定一个常数r(r>=1并且r<p),使得 x ^ 3=r ^ 3 - a mod p 无根。

2.3.3.确定一个复数根,对这个复数根作复数的快速幂运算,指数是(p^2+p+1)/3,最终结果就是需要的根。

时间复杂度为 O((log p)^3)。

额外空间复杂度为 O(1)。

go完整代码如下:

package main

import (
	"fmt"
	"math/big"
)

func main() {
	if true {

		if false {
			p := big.NewInt(0)
			p.SetString("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16)
			for c := big.NewInt(20000); c.Cmp(big.NewInt(30000)) <= 0; c.Add(c, big.NewInt(1)) {
				fmt.Println("c = ", c, "-------------")
				r := ModCbrt(c, p)
				fmt.Println("答案:", r)
				for i := 0; i < len(r); i++ {
					if big.NewInt(0).Exp(r[i], big.NewInt(3), p).Cmp(c) == 0 {

					} else {
						fmt.Println("答案错误", r[i], ",c = ", big.NewInt(0).Exp(r[i], big.NewInt(3), p))
						return
					}
				}
			}
			return
		}
		if true {
			p := big.NewInt(0)
			p.SetString("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16)
			for c := big.NewInt(20000); c.Cmp(big.NewInt(30000)) <= 0; c.Add(c, big.NewInt(1)) {
				fmt.Println("c = ", c, "-------------")
				r := ModCbrt(c, p)
				fmt.Println("答案:", r)
				for i := 0; i < len(r); i++ {
					if big.NewInt(0).Exp(r[i], big.NewInt(3), p).Cmp(c) == 0 {

					} else {
						fmt.Println("答案错误", r[i], ",c = ", big.NewInt(0).Exp(r[i], big.NewInt(3), p))
						return
					}
				}
			}
			return
		}

		if true {
			p := big.NewInt(997)
			for c := big.NewInt(1); c.Cmp(big.NewInt(0).Add(p, big.NewInt(-1))) <= 0; c.Add(c, big.NewInt(1)) {
				fmt.Println("c = ", c, "-------------")
				r := ModCbrt(c, p)
				fmt.Println("答案:", r)
				for i := 0; i < len(r); i++ {
					if big.NewInt(0).Exp(r[i], big.NewInt(3), p).Cmp(c) == 0 {

					} else {
						fmt.Println("答案错误", r[i], ",c = ", big.NewInt(0).Exp(r[i], big.NewInt(3), p))
						return
					}
				}
			}
		}
		return
	}
	fmt.Println("")
}

// 求模立方根的个数0,1,3
func ModCbrtCount(c, p *big.Int) int {
	t := big.NewInt(0)
	t.Add(p, big.NewInt(-2))
	t.Mod(t, big.NewInt(3))
	if t.Cmp(big.NewInt(0)) == 0 {
		return 1
	}
	t = big.NewInt(0).Add(p, big.NewInt(-1))
	t.Div(t, big.NewInt(3))
	if big.NewInt(0).Exp(c, t, p).Cmp(big.NewInt(1)) == 0 {
		return 3
	} else {
		return 0
	}
}

// Peralta Method
func ModCbrt(a, p *big.Int) (ans []*big.Int) {
	ans = make([]*big.Int, 0)
	count := ModCbrtCount(a, p)
	if count == 1 { //有1个解
		t := big.NewInt(0).Lsh(p, 1)
		t.Mod(t, p)
		t = t.Add(t, big.NewInt(-1))
		t.Mod(t, p)
		t.Mul(t, big.NewInt(0).ModInverse(big.NewInt(3), p))
		t.Mod(t, p)
		ans = append(ans, big.NewInt(0).Exp(a, t, p))
	} else if count == 3 { //有3个解,Peralta Method算法

		w := big.NewInt(0)
		p3 := big.NewInt(0).Add(p, big.NewInt(-1)) //(p-1)/3
		p3.Mul(p3, big.NewInt(0).ModInverse(big.NewInt(3), p))
		p3.Mod(p3, p)
		for i := big.NewInt(1); i.Cmp(p) < 0; i.Add(i, big.NewInt(1)) {
			w.Exp(i, p3, p)
			if w.Cmp(big.NewInt(1)) != 0 {
				break
			}
		}
		var x *big.Int
		key := big.NewInt(0)
		for x = big.NewInt(1); x.Cmp(p) < 0; x.Add(x, big.NewInt(1)) {
			key.Exp(x, big.NewInt(3), p) //key=x^3-a
			key.Add(key, big.NewInt(0).Neg(a))
			key.Mod(key, p)
			if key.Cmp(big.NewInt(0)) != 0 && ModCbrtCount(key, p) == 0 {
				break
			}
		}
		r := Ring{x, big.NewInt(0).Add(p, big.NewInt(-1)), big.NewInt(0), key}
		pp := big.NewInt(0).Mul(p, p) // pp = (p*p+p+1)/3,注意pp是不能 mod p的,有点反直觉
		pp.Add(pp, p)
		pp.Add(pp, big.NewInt(1))
		pp.Div(pp, big.NewInt(3))
		ansr := powerModI(r, pp, p)
		ans0 := ansr.a
		ans1 := big.NewInt(0)
		ans1.Mul(ans0, w)
		ans1.Mod(ans1, p)
		ans2 := big.NewInt(0)
		ans2.Mul(ans1, w)
		ans2.Mod(ans2, p)
		ans = append(ans, ans0, ans1, ans2)
	}
	return
}

type Ring struct {
	a *big.Int
	b *big.Int
	c *big.Int
	w *big.Int
}

// 复数乘法
func mulI(x Ring, y Ring, p *big.Int) Ring {
	var res Ring
	res.a = big.NewInt(0)
	res.b = big.NewInt(0)
	res.c = big.NewInt(0)
	res.w = x.w
	w := x.w

	a1 := big.NewInt(0)
	a2 := big.NewInt(0)
	a3 := big.NewInt(0)
	a1.Mul(x.a, y.a) //x.a*y.a
	a1.Mod(a1, p)
	a2.Mul(x.b, y.c) //x.b*y.c*key
	a2.Mod(a2, p)
	a2.Mul(a2, w)
	a2.Mod(a2, p)
	a3.Mul(x.c, y.b) //x.c*y.b*key
	a3.Mod(a3, p)
	a3.Mul(a3, w)
	a3.Mod(a3, p)
	res.a.Add(a1, a2)
	res.a.Mod(res.a, p)
	res.a.Add(res.a, a3)
	res.a.Mod(res.a, p)

	b1 := big.NewInt(0)
	b2 := big.NewInt(0)
	b3 := big.NewInt(0)
	b1.Mul(x.a, y.b) //x.a*y.b
	b1.Mod(b1, p)
	b2.Mul(x.b, y.a) //x.b*y.a
	b2.Mod(b2, p)
	b3.Mul(x.c, y.c) //x.c*y.c*key
	b3.Mod(b3, p)
	b3.Mul(b3, w)
	b3.Mod(b3, p)
	res.b.Add(b1, b2)
	res.b.Mod(res.b, p)
	res.b.Add(res.b, b3)
	res.b.Mod(res.b, p)

	c1 := big.NewInt(0)
	c2 := big.NewInt(0)
	c3 := big.NewInt(0)
	c1.Mul(x.a, y.c) //x.a*y.c
	c1.Mod(c1, p)
	c2.Mul(x.b, y.b) //x.b*y.b
	c2.Mod(c2, p)
	c3.Mul(x.c, y.a) //x.c*y.a
	c3.Mod(c3, p)
	res.c.Add(c1, c2)
	res.c.Mod(res.c, p)
	res.c.Add(res.c, c3)
	res.c.Mod(res.c, p)

	return res
}

// 复数快速幂,注意b不能取模
func powerModI(a Ring, b, p *big.Int) Ring {
	res := Ring{big.NewInt(1), big.NewInt(0), big.NewInt(0), a.w}
	for b.Cmp(big.NewInt(0)) != 0 {
		if big.NewInt(0).Mod(b, big.NewInt(2)).Cmp(big.NewInt(1)) == 0 {
			res = mulI(res, a, p)
		}
		a = mulI(a, a, p)
		b.Rsh(b, 1)
	}
	return res
}

在这里插入图片描述

标签:12,big,质数,整数,立方根,复数,go,mod
From: https://www.cnblogs.com/moonfdd/p/17872113.html

相关文章

  • 【C语言】【二级】移动一维数组中的内容;若数组中有n个整数,要求把下标从0到p的数组元
    题目请编写函数fun,函数的功能是:移动一维数组中的内容;若数组中有n个整数,要求把下标从0到p(含p,p小于等于n-1)的数组元素平移到数组的最后。例如,一维数组中的原始内容为:1,2,3,4,5,6,7,8,9,10;p的值为3。移动后,一维数组中的内容应为:5,6,7,8,9,10,1,2,3,4。考点一维数组、......
  • js和python获取1-100之间的质数
    jsfor(leti=2;i<=100;i++){letiszs=truefor(letj=2;j<i;j++){if(i%j===0){iszs=falsebreak}}if(iszs){zs.push(i)}}console.log(zs)pythonzs=[]foriinrange(2,101):iszs......
  • 未出现的最小非负整数(MEX)
    典题合集前置芝士[Set做法]structMex{//自定义N的大小 intcnt[N];//cnt(i)表示数字i出现的次数 set<int>st;//记录未出现的数字 multiset<int>mulst;//记录出现过的数字 Mex(){ for(inti=0;i<N;++i)cnt[i]=0; for(inti=0;i<N;++i)st.insert(......
  • 郑轻工 3097. 筛质数 + 二分 = 小模拟
    importjava.util.Arrays;importjava.util.Scanner;classMain{staticint[]pri=newint[100];staticintidx;publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intx=sc.nextInt();init......
  • 生成6位随机正整数
    使用Random生成随机数publicstaticStringgetStringRandom(){Randomrandom=newRandom();Stringstr=String.valueOf(random.nextInt(9));for(inti=0;i<5;i++){str+=random.nextInt(9);}returnstr;}使用Math生成随机数......
  • Sumsets(UVA10125)整数集合
    备课的时候发现了这道题,对于初识哈希来说并不算一道很简单的题。在查阅林厚从老师的示例代码与往届OI选手的博客后,大致理解了本题的思路。相关标签:Hash跳转至本题Description给定一个整数集合S,求一个最大的d,满足a+b+c=d,其中a,b,c,d∈SInput多组数据,每组数据包括:第一行一......
  • 001反转一个3位整数
    1.问题描述反转一个只有3位数的整数。2.示例输入num=123,输出321,输入num=100,输出1. 3.代码示例3.1python1classSolution:2defreverseInt(self,num):3ifisinstance(num,int)andnum<999andnum>99:4hundreds=int(num/1......
  • 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整
    示例:给定nums=[2,7,11,15],target=9因为nums[0]+nums[1]=2+7=9所以返回[0,1]用数组的indexOf()方法来查找值vartowSum=function(nums,target){for(leti=0,len=nums.length;i<len;i++){if(nums.indexOf(target-nums[i])>-1......
  • 算法~让整数从指定范围开始
    题目有个需求,我有4种类型,每种类型又有自己的数列,问我如何用一个数字来表示它们思路可以看一下java里的线程的实现,它是将一个int64的数字进行分区,每个区间代表一种状态,如运行中,挂起,暂停等,我们也可以通过这个方法来实现。实现在int32中,我找一个范围,存储我的运行中状态的数列,为......
  • 代码随想训练营第三十九天(Python)| 62.不同路径、63. 不同路径 II、343. 整数拆分
    62.不同路径classSolution:defuniquePaths(self,m:int,n:int)->int:#dp[i][j]代表到达dp[i][j]有多少不同路径dp=[[0]*nfor_inrange(m)]#初始化foriinrange(m):dp[i][0]=1forjinra......