1 | /* -*- mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ |
---|
2 | // vim:sts=8:sw=8:ts=8:noet:sr:cino=>s,f0,{0,g0,(0,\:0,t0,+0,=s |
---|
3 | /* linbox/algorithms/ |
---|
4 | * Copyright (C) 2005 Pascal Giorgi |
---|
5 | * |
---|
6 | * Written by Pascal Giorgi <pgiorgi@uwaterloo.ca> |
---|
7 | * |
---|
8 | * This library is free software; you can redistribute it and/or |
---|
9 | * modify it under the terms of the GNU Lesser General Public |
---|
10 | * License as published by the Free Software Foundation; either |
---|
11 | * version 2 of the License, or (at your option) any later version. |
---|
12 | * |
---|
13 | * This library is distributed in the hope that it will be useful, |
---|
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
---|
16 | * Lesser General Public License for more details. |
---|
17 | * |
---|
18 | * You should have received a copy of the GNU Lesser General Public |
---|
19 | * License along with this library; if not, write to the |
---|
20 | * Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor, |
---|
21 | * Boston, MA 02110-1301, USA. |
---|
22 | */ |
---|
23 | |
---|
24 | |
---|
25 | #ifndef __LINBOX_random_fftprime_H |
---|
26 | #define __LINBOX_random_fftprime_H |
---|
27 | |
---|
28 | #include "linbox/integer.h" |
---|
29 | #include "linbox/util/timer.h" |
---|
30 | |
---|
31 | namespace LinBox |
---|
32 | { |
---|
33 | |
---|
34 | class RandomFFTPrime { |
---|
35 | public: |
---|
36 | |
---|
37 | int _bits; |
---|
38 | |
---|
39 | RandomFFTPrime(int bits = 20, unsigned long seed = 0) : |
---|
40 | _bits(bits) |
---|
41 | { |
---|
42 | if (! seed) |
---|
43 | RandomFFTPrime::setSeed( (unsigned long)BaseTimer::seed() ); |
---|
44 | else |
---|
45 | RandomFFTPrime::setSeed( seed ); |
---|
46 | } |
---|
47 | |
---|
48 | // define the prime type |
---|
49 | typedef integer Prime_Type; |
---|
50 | |
---|
51 | /** @brief randomPrime() |
---|
52 | * return a random prime |
---|
53 | */ |
---|
54 | inline Prime_Type randomPrime() const |
---|
55 | { |
---|
56 | integer tmp; |
---|
57 | size_t cbits=5; |
---|
58 | size_t tresh; |
---|
59 | do { |
---|
60 | tresh = 1<<(cbits); |
---|
61 | size_t p = 1<<((size_t)_bits-cbits); |
---|
62 | do { |
---|
63 | integer::random(tmp,cbits); |
---|
64 | tmp = tmp*p+1; |
---|
65 | tresh--; |
---|
66 | } while (( Givaro::probab_prime(tmp)<2) && (tresh)); |
---|
67 | cbits++; |
---|
68 | } |
---|
69 | while(tresh==0); |
---|
70 | return tmp; |
---|
71 | } |
---|
72 | |
---|
73 | /** @brief randomPrime(Prime_Type& p) |
---|
74 | * return a random prime |
---|
75 | */ |
---|
76 | inline Prime_Type randomPrime (Prime_Type& t) const |
---|
77 | { |
---|
78 | size_t cbits=5; |
---|
79 | size_t tresh; |
---|
80 | do { |
---|
81 | tresh = 1<<(cbits); |
---|
82 | size_t p = 1<<((size_t)_bits-cbits); |
---|
83 | do { |
---|
84 | integer::random(t,cbits); |
---|
85 | t = t*p+1; |
---|
86 | tresh--; |
---|
87 | } while (!Givaro::probab_prime(t) && (tresh)); |
---|
88 | cbits++; |
---|
89 | } |
---|
90 | while(tresh==0); |
---|
91 | |
---|
92 | return t; |
---|
93 | } |
---|
94 | |
---|
95 | /** @brief setSeed (unsigned long ul) |
---|
96 | * Set the random seed to be ul. |
---|
97 | */ |
---|
98 | void static setSeed(unsigned long ul) |
---|
99 | { |
---|
100 | integer::seeding(ul); |
---|
101 | } |
---|
102 | |
---|
103 | |
---|
104 | }; |
---|
105 | } |
---|
106 | |
---|
107 | #endif //__LINBOX_random_fftprime_H |
---|
108 | |
---|