| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 30813 人关注过本帖
标题:各位老师好!求助编辑一个大整数的快速乘除法可调用程序
只看楼主 加入收藏
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
RSA公钥密码体制是上世纪70年代~80年代好像是,由3个数学家弄出来的,RSA分别是3位数学家的名字的开首字母。
这个原理就是前面证明过程中的衡等式:m^(ed)=m(mod n)。
数学家居然把它拆开成两个等式,两个过程,没有反例,不会出错。

[此贴子已经被作者于2020-3-3 15:43编辑过]

2020-03-03 15:40
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
比较这两个公式:a^p≡a(mod p)(费马小定理),m^(ed)=m(mod n)(欧拉原理)(其中ed=1(mod  φ(n)),n为素数也成立)
显然二者不同,不能同日而语。
2020-03-03 16:46
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
辛苦了!数学渣,要慢慢消化。

能编个毛线衣吗?
2020-03-03 21:19
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
回复 193楼 wmf2014
谢谢你的帮助!一点儿小知识供参考!非常感谢您关注沟通和指导!
2020-03-03 22:11
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
重发一下欧拉定理的证明,是网上摘录复制过来的:(帮助理解或参考了解一下)
数论定理
内容
在数论中,欧拉定理,(也称费马-欧拉定理)是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互质,则:
a^[φ(n)]≡1 (mod n)
证明
将1~n中与n互质的数按顺序排布:x1,x2……xφ(n) (显然,共有φ(n)个数)
我们考虑这么一些数:
m1=a*x1;m2=a*x2;m3=a*x3……mφ(n)=a*xφ(n)
1)这些数中的任意两个都不模n同余,因为如果有mS≡mR (mod n) (这里假定mS更大一些),就有:
mS-mR=a(xS-xR)=qn,即n能整除a(xS-xR)。但是a与n互质,a与n的最大公因子是1,而xS-xR<n,因而左式不可能被n整除。也就是说这些数中的任意两个都不模n同余,φ(n)个数有φ(n)种余数。
2)这些数除n的余数都与n互质,因为如果余数与n有公因子r,那么a*xi=pn+qr=r(……),a*xi与n不互质,而这是不可能的。(因为a*xi=pn+qr=r(……),说明a*xi含有因子r,又因为前面假设n含有因子r,所以a*xi和n含有公因子r,因此a*xi与n不互质)那么这些数除n的余数,都在x1,x2,x3……xφ(n)中,因为这是1~n中与n互质的所有数,而余数又小于n.
由1)和2)可知,数m1,m2,m3……mφ(n)(如果将其次序重新排列)必须相应地同余于x1,x2,x3……xφ(n).
故得出:m1*m2*m3……mφ(n)≡x1*x2*x3……xφ(n) (mod n)
或者说a^[φ(n)]*(x1*x2*x3……xφ(n))≡x1*x2*x3……xφ(n)(mod n)
或者为了方便:K{a^[φ(n)]-1}≡0 ( mod n ) 这里K=x1*x2*x3……xφ(n)。
可知K{a^[φ(n)]-1}被n整除。但K中的因子x1,x2……都与n互质,所以K与n互质。那么a^[φ(n)]-1必须能被n整除,即a^[φ(n)]-1≡0 (mod n),即a^[φ(n)]≡1 (mod n),得证。
费马小定理:
a是不能被质数p整除的正整数,则有a^(p-1) ≡ 1 (mod p)
证明这个定理非常简单,由于p是质数,所以有φ(p) = p-1,代入欧拉定理即可证明。推论:对于任意正整数a,有a^p ≡ a (mod p),因为a能被p整除时结论显然成立。

[此贴子已经被作者于2020-3-3 22:56编辑过]

2020-03-03 22:53
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
  等式m^(ed)=m(mod n)可以用欧拉定理的推论简单证明的,证明如下:
证明:根据欧拉定理的推论,
若正整数a,n互质,那么对于任意正整数b,有a^b≡a^(b mod φ(n))(mod n)。
令b=ed,则m^(ed)=m^b,由于ed=1(mod  φ(n)),所以m^(b mod φ(n))=m (mod n)。
证毕!
2020-03-04 11:06
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
发现自己在快速幂模上的一个错误,昨天给的测试速度和结果并不准确。修正后运行速度不及你的快速幂模算法,在网上找了个100位的素数,改用你的快速幂模算法后测得的执行速度为1.5秒,感觉还是太慢。
准备入手快速乘法,不打算用fft,感觉它是使用乘法多项式的,不能够得到精确结果,打算用分治法实现,希望对运算速度有所提升。
分治法乘法举例:38*96=3648
第一步:3*9=27   第二步:8*6=48    第三步:(3+8)*(9+6)=165    第四步:165-48-27=90   第五步拼接:2700+900+48=3648
两位数乘法分治法共做乘法3次,加法4次,减法两次,比传统竖式算法少做一次乘法,在50位以内可能比传统算法还慢,位数越大提速应该月明显,最终乘法次数可达到n(log n)(传统次数是n^2),应该有显著的提速。
图片附件: 游客没有浏览图片的权限,请 登录注册

能编个毛线衣吗?
2020-03-04 15:09
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
回复 197楼 wmf2014
谢谢您!fft我也至今不会,能提高速度就好!
2020-03-04 16:14
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
下面的vc程序朋友给了注释,看懂的老师请给翻译成为vb程序:

//下面是网上找到的用vc编程的fft快速高精度乘法程序,我看不懂,请看看,翻译成vb可调用程序,谢谢!
//cp可定义变量为复数
#include<bits/stdc++.h>
using namespace std;
//complex是stl自带的定义复数的容器
typedef complex<double> cp;
#define N 2097153
//定义pie=表示圆周率π 这个常数
const double pie=acos(-1);
int n;
//定义n为(?)数
cp a[N],b[N];
//定义a[N],b[N]为复数
int rev[N],ans[N];
char s1[N],s2[N];
//读入优化
//定义 rev[N],ans[N]为整数数组
//定义s1[N],s2[N]为字符数组
int read(){ //函数
    int sum=0,f=1; //定义为整数并赋初值
    char ch=getchar();//屏幕输入一个字符
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
//如果ch为“-”让f=-1,ch=getchar(),屏幕输入一个字符
//循环保证读到的字符为数字
    while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
//如果字符为数值执行以下
//“sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar()”输入数字(?看不清是啥字)
    return sum*f;
}  //读入一个带正负号的整数(合?看不清啥字)
//初始化每个位置最终到达的位置
{
    int len=1<<k; //定义len为整数并赋值len=2^k,朋友给出的注释,发的手工写的图片后面还多不清楚不发了。
    for(int i=0;i<len;i++)
    rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
}
//a表示要操作的系数,n表示序列长度
//若flag为1,则表示FFT,为-1则为IFFT(需要求倒数)
void fft(cp *a,int n,int flag){
    for(int i=0;i<n;i++)
    {
     //i小于rev[i]时才交换,防止同一个元素交换两次,回到它原来的位置。
      if(i<rev[i])swap(a[i],a[rev[i]]);
    }
    for(int h=1;h<n;h*=2)//h是准备合并序列的长度的二分之一
    {
    cp wn=exp(cp(0,flag*pie/h));//求单位根w_n^1
     for(int j=0;j<n;j+=h*2)//j表示合并到了哪一位
     {
      cp w(1,0);
       for(int k=j;k<j+h;k++)//只扫左半部分,得到右半部分的答案
       {
         cp x=a[k];
         cp y=w*a[k+h];
         a[k]=x+y;  //这两步是蝴蝶变换
         a[k+h]=x-y;
         w*=wn; //求w_n^k
       }
     }
     }
     //判断是否是FFT还是IFFT
     if(flag==-1)
     for(int i=0;i<n;i++)
     a[i]/=n;
}
int main(){
    n=read();
    scanf("%s%s",s1,s2);
    //读入的数的每一位看成多项式的一项,保存在复数的实部
    for(int i=0;i<n;i++)a[i]=(double)(s1[n-i-1]-'0');
    for(int i=0;i<n;i++)b[i]=(double)(s2[n-i-1]-'0');
    //k表示转化成二进制的位数
    int k=1,s=2;
     while((1<<k)<2*n-1)k++,s<<=1;
    init(k);
    //FFT 把a的系数表示转化为点值表示
    fft(a,s,1);
    //FFT 把b的系数表示转化为点值表示
    fft(b,s,1);
    //FFT 两个多项式的点值表示相乘
    for(int i=0;i<s;i++)
    a[i]*=b[i];
    //IFFT 把这个点值表示转化为系数表示
    fft(a,s,-1);
    //保存答案的每一位(注意进位)
    for(int i=0;i<s;i++)
    {
    //取实数四舍五入,此时虚数部分应当为0或由于浮点误差接近0
    ans[i]+=(int)(a[i].real()+0.5);
    ans[i+1]+=ans[i]/10;
    ans[i]%=10;
    }
    while(!ans[s]&&s>-1)s--;
    if(s==-1)printf("0");
    else
    for(int i=s;i>=0;i--)
    printf("%d",ans[i]);
    return 0;
}
2020-03-06 14:13
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
下面是朋友发的最后3张图片:
图片附件: 游客没有浏览图片的权限,请 登录注册
图片附件: 游客没有浏览图片的权限,请 登录注册
图片附件: 游客没有浏览图片的权限,请 登录注册
2020-03-06 14:19
快速回复:各位老师好!求助编辑一个大整数的快速乘除法可调用程序
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.025571 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved