随机获取特定长度的素数（32bits）（拉宾米勒算法）
ckfan
posted @ 2012年10月16日 14:48
in 技术blog
with tags
拉宾米勒算法 素数 随机
, 1049 阅读
这是在is-programmer的第一篇blog，拉宾米勒算法由一同学提供，谢谢他！
#define type int
type get_rand()
{
type a;
a = rand();
a* = rand();
return abs(a);
}
/******a^b mod c *******/
type PowerMod(type a, type b, type c)
{
type r =1 ;
while(b)
{
if( b & 1 )
{
r = r * a % c;
}
b >>= 1;
a = a * a % c;
}
return r;
}
/********* 素数随机判定算法 *******/
type mod_mul (type x , type y , type n)
{
type T =(type)( sqrt((double)n) + 0.5);
type t = T * T - n;
type a = x / T;
type b = x %T;
type c = y / T;
type d = y % T;
type e = a * c / T;
type f = a * c % T;
type v = (( a * d + b * c) % n + e * t ) % n;
type g = v / T;
type h = v % T;
type ans = ((( f + g) * t % n + b * d) % n + h * T) % n;
while ( ans < 0)
ans += n;
return ans ;
}
/*
米勒-拉宾法算法
*/
type Rabin_Miller(type n)
{
type k = 0, i, j, m, a;
if( n < 2)
return 0;
if(n == 2)
return 1;
if( !(n & 1) )
return 0;
m = n - 1;
while( !( m & 1 ) )
m >>= 1, k++;
for(i = 0; i < 10; i++)
{
a = get_rand() % (n - 2) + 2;
a = PowerMod(a, m, n);
if(a == 1)
continue;
for(j = 0; j < k; j++)
{
if(a == n-1)
break;
a = mod_mul(a, a, n);
}
if(j < k)
continue;
return 0;
}
return 1;
}
/*
获取特定长度的随机素数
*/
type Get_Rand_Prime(type bytes)
{
type i;
type prime;
bytes = 0;
prime = 0;
i = 0;
while (1)
{
prime = 0;
i = bytes;
while(i--)
{
prime = prime * 10 + rand() % 10;
if (i ==( bytes - 1) && prime == 0)
{
prime = 1;
}
}
prime = prime | 0x01;
if (Rabin_Miller(prime))
{
break;
}
}
return prime;
}
2024年2月24日 14:57
little garage door troubleshooting can go a long way in maintaining your door’s build and functionality. Because of the quantity of cycles your garage door endures through daily use, garage door repairs and annual maintenance are commo
2024年9月08日 20:59
The articles passed on your site are genuinely contributing towards my homework. I’m not a shocking energetic adult concerning considering, and I, generally speaking, mission for pivotal courses.
2024年9月08日 21:00
Buy Women Panties online at the best price in India. Choose Topwear for men from a wide range of options available at our online shopping store TT Bazaar. Buy mens bottomwear online of high quality at a discounted price. TT Bazaar brings an extensive collection, making mens bottomwear online shopping fun.
2024年9月08日 21:02
We and our whole young Gurgaon Escorts put stock in spreading like and fulfilment of everything about and this is the technique. We are young ladies in Haryana who have the genuine and best feelings for sex and give you a superior. Our young ladies give you quick and long call girl service and you get a kick out of the chance to be petted, kissed, embraced, moved, and provoked which makes you completely happy with the Gurgaon Escorts benefit. You will be especially energised once you invest energy with her. She was giving you extraordinary fun which you never go anywhere. We are not young ladies who simply need to create wages and not give you inviting services and simply rest. Independent young ladies in Haryana are incorporated totally into the demonstration and give you a vibe of real closeness. Because the best service and young ladies claim techniques to get you satisfied and you acknowledge sex benefits most charmingly. We know extremely well what makes men crazy. We never let her away doing all the little compelling variables to give benefits to Gurgaon Escorts.
2024年9月08日 21:04
We have the best escorts in the world in our Elite Escort Collection. We are proud to offer you the best Lahore Escorts at reasonable prices. Women Call Girls in Lahore has the best Escort agency in Lahore, and our high salary rate ensures that you get the most professional, friendly, and discerning female escorts to join our team.
2024年9月08日 21:05
Quality content is the main to be a focus for the people to visit the web..page, that’s what this web site is providing.I am sure this paragraph has touched all the internet visitors,..its really really good piece of writing on building up new.Heya i’m for the primary time here. I came across this board and I find It really useful & it helped me out much
2024年9月08日 21:36
Buy Women Panties online at the best price in India. Choose Topwear for men from a wide range of options available at our online shopping store TT Bazaar. Buy mens bottomwear online of high quality at a discounted price. TT Bazaar brings an extensive collection, making mens bottomwear online shopping fun.
2024年9月08日 21:37
Are you looking for assignment help services in Canada? To help students with their assignments, our team provides the most affordable assignment writing services. Hire our highly educated team of professionals to help you achieve good scores on all of your university and college assignments. Please contact us immediately!
2024年9月08日 21:38
8 Ball Pool Cheats will let you buy all items for free. Below you will see all the cheats needed to hack 8 Ball Pool These Cheats for 8 Ball Pool work on all iOS and Android devices. You will also not need a jailbreak or rooted phone. Using our website you no longer need to download a hack tool, so it is safer. If you don't know how to use the hack for 8 Ball Pool hack tool then
2024年9月08日 21:39
We offer hot and beautiful girls for escorts. We are pleased to announce that we’re the biggest call girl provider and that our models are gorgeously attractive, fashionable and fashionable and educated. They are authentically represented in their portfolios. We also offer top-quality and VIP Escorts. Our girls are experienced and have previous experience with escorts. They will offer you the most memorable experiences and an unforgettable experience you’ll not forget. Our ladies’ companions are skilled and peaceful and comfortable. We provide a variety of female escorts. Contact us to learn more or to hire our female escorts at any time. Our escorts services are available all hours of the day.
2024年9月08日 21:39
In the present computerized age, the world has seen a change in how administrations are conveyed and gotten to, with the domain of escort service being no exemption. With stages like Kudilo, the web-based scene of Chandigarh Escort Service has seen an insurgency, smoothing out the interaction for clients and guaranteeing a more significant level of privacy and comfort.
2024年9月08日 21:41
In the present computerized age, the world has seen a change in how administrations are conveyed and gotten to, with the domain of escort service being no exemption. With stages like Kudilo, the web-based scene of Chandigarh Escort Service has seen an insurgency, smoothing out the interaction for clients and guaranteeing a more significant level of privacy and comfort.
2024年9月08日 22:34
I keep hearing Escorts talk about getting free online grant applications. If you are looking for the most excellent site to get such a website. So you can please talk to me, I will take you to such a website that your search will end.
2024年9月08日 22:36
Thanks for a marvelous posting! I definitely enjoyed reading it, you’re a great author. I will ensure that I bookmark your blog and will come back sometime soon. I want to encourage that you continue your great work, have a nice day! My site address
2024年9月08日 22:41
When you have insufficient time or less knowledge of the assigned topic and you can’t write your assignment easily and facing problems while writing your assignments for UK universities, in this situation you can contact the best assignment help online and get quality writing help from expert assignment writers. With Best Assignment Help UK you can grab the support of experts and get high grades in your exams.
2024年9月08日 22:42
I wish more authors of this type of content would take the time you did to research and write so well. I am very impressed with your vision and insight.
2024年9月08日 22:42
Very useful information shared in this article, nicely written! I will be reading your articles and using the informative tips. Looking forward to read such knowledgeable articles.
2024年9月08日 22:43
I am really impressed with your writing skills well with the layout for your weblog. Is that this a paid subject matter or did you modify it your self? Anyway stay up the nice high quality writing, it is rare to see a nice weblog like this one these days
2024年9月08日 22:47
wow, great, I was wondering how to cure acne naturally. and found your site by google, learned a lot, now i’m a bit clear. I’ve bookmark your site and also add rss. keep us updated.
2024年9月08日 22:50
Wow, cool post. I'd like to write like this too - taking time and real hard work to make a great article... but I put things off too much and never seem to get started. Thanks though.
2024年9月08日 23:15
Can I simply say what a relief to get any individual that genuinely knows what theyre discussing over the net. You sincerely apprehend how to carry a venture to mild to make it vital. More and greater humans have to see this and apprehend this facet of the story. I cant believe youre less common when you really maintain the present.
2024年9月08日 23:37
wow, great, I was wondering how to cure acne naturally. and found your site by google, learned a lot, now i’m a bit clear. I’ve bookmark your site and also add rss. keep us updated.