【C# 每日一题10】a^b % c = d,该如何处理

【C# 每日一题10】a^b % c = d
看题目大家就知道这个是个数学问题了吧？
此贴目的在于让大妞们给咱们普及一下数学知识！

问题1

C# code

Description现有一公式：a^b mod c = X.给出a,b,c，求X。注：c总是素数InputOutputSample Input3 8 132 3 11Sample Output38

大牛们一定知道如何快速的求这个问题1吧！！

之后还有问题2

C# code

Description现有一公式：X^a mod b = c.给出a,b,c，求出所有满足条件的X。输入包括多组数据，每组数据三个正整数1<=a,b,c<=10^7。每组数据输出若干行，每一行代表了满足方程的一个X的解，解的顺序按照从小到大输出,最后输出一个空行。没有解输出“No Solution!”注：b总是素数InputOutputSample Input3 13 82 3 2Sample Output258

这个问题如何解决呢？

求大牛们的思想，求大神们的代码！谢谢大家的参与！
鼓掌

PS：这个帖子是最后一题了，过两天就要回学校啦！
哈哈，回来有时间的话就继续发！

谢谢版主，大神，大牛们的提携鼓励，让我们学到了好多的东西！

谢谢大家的参与！


[解决办法]
记得可以对a^b mod c = X进行化简的，唉，老做这个，俺都开始没有兴趣了。
[解决办法]
套公式，A*B mod C=（（A mod C)*（B mod C) mod C ；A^B mod C=(A mod C)^(B mod C) mod C。
这题我不折腾了！！我围观了 ^_^

[解决办法]
问题1

C# code

        static void Main(string[] args)        {            int r = 0;            r = Fx(3, 8, 13);            Console.Write(r);            r = Fx(2, 3, 11);            Console.Write(r);            Console.Read();        }        static int Fx(int a, int b, int c)        {            int t = b >> 1;            return (t>0?Fx((a*a)%c,t,c):1)*((b & 1)==0?1:a % c) % c;        }
[解决办法]
探讨

引用:

问题1
C# code
static void Main(string[] args)
{
int r = 0;
r = Fx(3, 8, 13);
Console.Write(r);
r = Fx(2, 3, 11);
Console.Wr……

大牛出现了！
求数学思想，求解释！
求第二题，求帮助！

[解决办法]
C# code
// Right-to-left binary methodint Modular(int theBase, int exponent, int modulus){    int result = 1;    while( exponent > 0 )    {        if( (exponent & 1) == 1 )        {            result = (result * theBase) % modulus;        }        exponent /= 2;        theBase = (theBase * theBase) % modulus;    }    return result;}
[解决办法]
第二题只想到这么一个算法
C# code
        static void FX2(int a, int b, int c)        {            while (c < 10000000)            {                double x = Math.Pow( Math.E ,Math.Log(c)/a);                if (Math.Round( x,8) == Math.Round(x))                {                    Console.WriteLine(Math.Round(x));                }                c += b;            }                    }
[解决办法]
a^b mod c = X
首先计算a^1 mod c = ? a^2 mod c = ? ,直到a^n mod c =1,然后n为循环，计算b mod n，最后求出余数。
3^8 mod 13 = 9 ,不是3
[解决办法]
第二题真没看懂,假定a=3 b=13 c=8

由 X^3 mod 13 = 8 可以推导得出 X^3=13*k +8(k为自然数)
由于k有无数个，可以推导出13k+8有无数个，等量替换，可以推导出X^3有无数个。从而可以得到，这样的X有无数个。。。。

我求出来 2，5，6，15，18，19，28，31，32，41，44，45，54，57，58，67，70，71，80，83....一大堆呢
[解决办法]
C# code
            string input = Console.ReadLine();            string[] nums = input.Split(' ');            int x, a, b, c, tempResult;            List<int> answer = new List<int>();            //a = Convert.ToInt32(nums[0]);            a = Convert.ToInt32(nums[0]);            b = Convert.ToInt32(nums[1]);            c = Convert.ToInt32(nums[2]);            for (x = 1; x <= 300; x++)            {                tempResult = 1;                for (int times = 1; times <= a; times++)                    tempResult *= x;                if (tempResult % b == c)                    answer.Add(x);            }            answer.ForEach(an => Console.WriteLine(an)); 
 
[解决办法]
很不好意思的问一下，a^b是xor还是pow？
[解决办法]
x^a mod b = c

其中的a和b形成了一个RSA公钥：
b就是RSA算法公钥中的Modulo
a就是RSA算法公钥中的D(Exponent)

c就是秘文。
能够找到一个通用算法来解出x，你就可以破解RSA加密，得到明文x :)

[解决办法]
rsa的数比这个要大多了，10^7以内的话还是可以弄的，至少穷举是一个办法。
今天上班忙，晚上回家再想想。另外由于本人数学底子比较薄，弄不好还得学习一些基本的数论知识，才能找到比较快的方法。

探讨

x^a mod b = c

其中的a和b形成了一个RSA公钥：
b就是RSA算法公钥中的Modulo
a就是RSA算法公钥中的D(Exponent)

c就是秘文。
能够找到一个通用算法来解出x，你就可以破解RSA加密，得到明文x :)

[解决办法]
第一题最简单:
C# code
(a**b) % c
[解决办法]
太热了，起早了。
昨天晚上想了一个构造1系列解的方法，能否推出所有解还不太清楚。
首先可以利用2次剩余（配合勒让德符号），在log(n)的时间里，构造一个m，使得m^2 mod b = c
以a = 9，b = 17，c = 8为例，先构造出m = 5
则5^(16n + 2) mod 17 = 2
这时利用欧几里得扩展解模方程，16y + 2 = 9z，也是log(n)的，当y = (9k + 1)时 z有整数解
当y = 1时，z = 2
令x = m^z = 5^2 = 25，则25 ^ 9 mod 17 = 8同时8^9 mod 17 = 42^9 mod 17 = 8
整个构造过程是log(n)的


[解决办法]
探讨


y的解的个数都不止log(n)个，怎么可能在O(log n)时间内计算出Y的所有可能解？
解本身是无数个，只是有x < 10^7的限制，才是有限个。

btw，浙大这次却是厉害。
引用:
第二题
X^a mod b = c
先设 Y = X ^ a;
则问题转化为 Y mod b = c;
转化为模线性方程为 Y == c(mod b)……
 

 

查看更多 下一篇