首页 > 其他 > 详细

poj 2417 Discrete Logging(A^x=B(mod c),普通baby_step)

时间:2014-08-11 21:19:33      阅读:411      评论:0      收藏:0      [点我收藏+]

http://poj.org/problem?id=2417


A^x = B(mod C),已知A,B,C,求x。

这里C是素数,可以用普通的baby_step。

在寻找最小的x的过程中,将x设为i*M+j。从而原始变为A^M^i * A^j = B(mod C),D = A^M,那么D^i * A^j = B(mod C ),

预先将A^j存入hash表中,然后枚举i(0~M-1),根据扩展欧几里得求出A^j,再去hash表中查找相应的j,那么x = i*M+j。

确定x是否有解,就是在循环i的时候判断相应A^j是否有解,而且最小的解x一定在(0~C-1),因为gcd(D^i,C) = 1.

如果(0~C-1)无解,那么一定无解。因为A^x%C(C是素数)有循环节,A^x%C = A^(x%phi[c])%C,循环节的长度为phi(C),即C-1,x >= C以后开始新一轮的循环,因此(0~C-1)内无解的话,一定无解。


#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)

using namespace std;
const int maxn = 499991;

bool hash[maxn+10];
int idx[maxn+10];
LL val[maxn+10];
//插入哈希表
void insert(int id, LL vv)
{
	int v = vv % maxn;
	while(hash[v] && val[v] != vv)
	{
		v++;
		if(v == maxn)
			v -= maxn;
	}
	if(!hash[v])
	{
		hash[v] = true;
		idx[v] = id;
		val[v] = vv;
	}
}
//查找vv对应的jj,A^jj = vv
int found(LL vv)
{
	int v = vv%maxn;
	while(hash[v] && val[v] != vv)
	{
		v++;
		if(v == maxn)
			v -= maxn;
	}
	if(hash[v] == false)
		return -1;
	return idx[v];
}

void extend_gcd(LL a, LL b, LL &x, LL &y)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		return;
	}
	extend_gcd(b,a%b,x,y);
	LL t = x;
	x = y;
	y = t-a/b*y;
}
/*
A^x = B(mod C)
令x = i*M+j, 其中M = ceil(sqrt(C*1.0)),(0 <= i,j < M)
那么原式变为A^M^i*A^j = B(mod c)
先枚举j(0~M-1),将A^j%C存入hash表中
令D = A^M%C,X = A^j,那么D^i*X = B(mod C)
枚举i(0~M-1)求得D^i设为DD,DD*X = B(mod C)
DD,C已知,根据扩展欧几里得求出X,在hash表中查找X对应的jj,即A^jj = X。
那么x = i*M+jj,若找不到jj无解。
*/
LL baby_step(LL A, LL B, LL C)
{
	memset(hash,false,sizeof(hash));
	memset(idx,-1,sizeof(idx));
	memset(val,-1,sizeof(val));

	LL M = ceil(sqrt(C*1.0));
	//将A^j存入hash表中
	LL D = 1;
	for(int j = 0; j < M; j++)
	{
		insert(j,D);
		D = D*A%C;
	}
	//D = A^M%C,res = D^i,求方程res*X = B(mod C)中的X,去找X对应的jj,那么x=i*M+jj.
	LL res = 1,x,y;
	for(int i = 0; i < M; i++)
	{
		extend_gcd(res,C,x,y);
		x = x*B;
		x = (x%C+C)%C;
		int jj = found(x);
		if(jj != -1)
		{
			return (LL)i*M+jj;
		}
		res = res*D%C;
	}
	return -1;
}

int main()
{
	LL A,B,C;
	while(~scanf("%lld %lld %lld",&C,&A,&B))
	{
		LL res = baby_step(A,B,C);
		if(res == -1)
			printf("no solution\n");
		else
			printf("%lld\n",res);
	}
	return 0;
}





poj 2417 Discrete Logging(A^x=B(mod c),普通baby_step),布布扣,bubuko.com

poj 2417 Discrete Logging(A^x=B(mod c),普通baby_step)

原文:http://blog.csdn.net/u013081425/article/details/38498573

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!