Commit | Line | Data |
---|---|---|

9a8b0c8d | 1 | /* -*-c-*- |

2 | * | |

b817bfc6 | 3 | * $Id: pfilt.h,v 1.4 2004/04/08 01:36:15 mdw Exp $ |

9a8b0c8d | 4 | * |

5 | * Finding and testing prime numbers | |

6 | * | |

7 | * (c) 1999 Straylight/Edgeware | |

8 | */ | |

9 | ||

45c0fd36 | 10 | /*----- Licensing notice --------------------------------------------------* |

9a8b0c8d | 11 | * |

12 | * This file is part of Catacomb. | |

13 | * | |

14 | * Catacomb is free software; you can redistribute it and/or modify | |

15 | * it under the terms of the GNU Library General Public License as | |

16 | * published by the Free Software Foundation; either version 2 of the | |

17 | * License, or (at your option) any later version. | |

45c0fd36 | 18 | * |

9a8b0c8d | 19 | * Catacomb is distributed in the hope that it will be useful, |

20 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |

21 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |

22 | * GNU Library General Public License for more details. | |

45c0fd36 | 23 | * |

9a8b0c8d | 24 | * You should have received a copy of the GNU Library General Public |

25 | * License along with Catacomb; if not, write to the Free | |

26 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, | |

27 | * MA 02111-1307, USA. | |

28 | */ | |

29 | ||

9a8b0c8d | 30 | #ifndef CATACOMB_PFILT_H |

31 | #define CATACOMB_PFILT_H | |

32 | ||

33 | #ifdef __cplusplus | |

34 | extern "C" { | |

35 | #endif | |

36 | ||

37 | /*----- Header files ------------------------------------------------------*/ | |

38 | ||

39 | #ifndef CATACOMB_MP_H | |

40 | # include "mp.h" | |

41 | #endif | |

42 | ||

34e4f738 | 43 | #ifndef CATACOMB_PRIMETAB_H |

9a8b0c8d | 44 | # include "primetab.h" |

45 | #endif | |

46 | ||

47 | /*----- Data structures ---------------------------------------------------*/ | |

48 | ||

49 | typedef struct pfilt { | |

50 | mp *m; | |

64d27fe0 | 51 | smallprime r[NPRIME]; |

9a8b0c8d | 52 | } pfilt; |

53 | ||

54 | /*----- Functions provided ------------------------------------------------*/ | |

55 | ||

64d27fe0 | 56 | /* --- @pfilt_smallfactor@ --- * |

57 | * | |

58 | * Arguments: @mp *m@ = integer to test | |

59 | * | |

60 | * Returns: One of the @PGEN@ result codes. | |

61 | * | |

62 | * Use: Tests a number by dividing by a number of small primes. This | |

63 | * is a useful first step if you're testing random primes; for | |

64 | * sequential searches, @pfilt_create@ works better. | |

65 | */ | |

66 | ||

67 | extern int pfilt_smallfactor(mp */*m*/); | |

68 | ||

9a8b0c8d | 69 | /* --- @pfilt_create@ --- * |

70 | * | |

71 | * Arguments: @pfilt *p@ = pointer to prime filtering context | |

72 | * @mp *m@ = pointer to initial number to test | |

73 | * | |

74 | * Returns: A @PGEN@ result code. | |

75 | * | |

76 | * Use: Tests an initial number for primality by computing its | |

77 | * residue modulo various small prime numbers. This is fairly | |

78 | * quick, but not particularly certain. If a @PGEN_TRY@ | |

79 | * result is returned, perform Rabin-Miller tests to confirm. | |

80 | */ | |

81 | ||

82 | extern int pfilt_create(pfilt */*p*/, mp */*m*/); | |

83 | ||

84 | /* --- @pfilt_destroy@ --- * | |

85 | * | |

86 | * Arguments: @pfilt *p@ = pointer to prime filtering context | |

87 | * | |

88 | * Returns: --- | |

89 | * | |

90 | * Use: Discards a context and all the resources it holds. | |

91 | */ | |

92 | ||

93 | extern void pfilt_destroy(pfilt */*p*/); | |

94 | ||

95 | /* --- @pfilt_step@ --- * | |

96 | * | |

97 | * Arguments: @pfilt *p@ = pointer to prime filtering context | |

98 | * @mpw step@ = how much to step the number | |

99 | * | |

100 | * Returns: One of the @PGEN@ result codes. | |

101 | * | |

102 | * Use: Steps a number by a small amount. Stepping is much faster | |

103 | * than initializing with a new number. The test performed is | |

104 | * the same simple one used by @primetab_create@, so @PGEN_TRY@ | |

105 | * results should be followed up by a Rabin-Miller test. | |

106 | */ | |

107 | ||

108 | extern int pfilt_step(pfilt */*p*/, mpw /*step*/); | |

109 | ||

110 | /* --- @pfilt_muladd@ --- * | |

111 | * | |

112 | * Arguments: @pfilt *p@ = destination prime filtering context | |

113 | * @const pfilt *q@ = source prime filtering context | |

114 | * @mpw m@ = number to multiply by | |

115 | * @mpw a@ = number to add | |

116 | * | |

117 | * Returns: One of the @PGEN@ result codes. | |

118 | * | |

119 | * Use: Multiplies the number in a prime filtering context by a | |

120 | * small value and then adds a small value. The destination | |

121 | * should either be uninitialized or the same as the source. | |

122 | * | |

123 | * Common things to do include multiplying by 2 and adding 0 to | |

124 | * turn a prime into a jump for finding other primes with @q@ as | |

125 | * a factor of @p - 1@, or multiplying by 2 and adding 1. | |

126 | */ | |

127 | ||

128 | extern int pfilt_muladd(pfilt */*p*/, const pfilt */*q*/, | |

129 | mpw /*m*/, mpw /*a*/); | |

130 | ||

131 | /* --- @pfilt_jump@ --- * | |

132 | * | |

133 | * Arguments: @pfilt *p@ = pointer to prime filtering context | |

134 | * @const pfilt *j@ = pointer to another filtering context | |

135 | * | |

136 | * Returns: One of the @PGEN@ result codes. | |

137 | * | |

138 | * Use: Steps a number by a large amount. Even so, jumping is much | |

139 | * faster than initializing a new number. The test peformed is | |

140 | * the same simple one used by @primetab_create@, so @PGEN_TRY@ | |

141 | * results should be followed up by a Rabin-Miller test. | |

142 | * | |

143 | * Note that the number stored in the @j@ context is probably | |

144 | * better off being even than prime. The important thing is | |

145 | * that all of the residues for the number have already been | |

146 | * computed. | |

147 | */ | |

148 | ||

149 | extern int pfilt_jump(pfilt */*p*/, const pfilt */*j*/); | |

150 | ||

151 | /*----- That's all, folks -------------------------------------------------*/ | |

152 | ||

153 | #ifdef __cplusplus | |

154 | } | |

155 | #endif | |

156 | ||

157 | #endif |