Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download
241818 views
Tweet
Share
Share
1
#ifndef _FFPOLY_INCLUDE

2
#define _FFPOLY_INCLUDE

3


4
#include "gmp.h"

5
#include "ff.h"

6


7
/*

8
    Copyright 2007 Andrew V. Sutherland

9


10
    This file is part of smalljac.

11


12
    smalljac is free software: you can redistribute it and/or modify

13
    it under the terms of the GNU General Public License as published by

14
    the Free Software Foundation, either version 2 of the License, or

15
    (at your option) any later version.

16


17
    smalljac is distributed in the hope that it will be useful,

18
    but WITHOUT ANY WARRANTY; without even the implied warranty of

19
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

20
    GNU General Public License for more details.

21


22
    You should have received a copy of the GNU General Public License

23
    along with smalljac.  If not, see <http://www.gnu.org/licenses/>.

24
*/

25


26
// This module consists mostly of functions that are probably better implemented in NTL

27
// but are handy for a standalone C implementation.

28


29
// The discriminant and resultant code is woefully incomplete

30


31
#define POLY_MAX_DEGREE			80

32
#define POLY_G2TOR3_DEGREE		40

33


34
// handy macros - these require integer variables d_f be declared for each poly f

35
#define _poly_set(a,b)				ff_poly_copy(a,&d_ ## a,b,d_ ## b)

36
#define _poly_print(a)				ff_poly_print(a,d_ ## a)

37
#define _poly_neg(c,a)				ff_poly_neg(c,&d_ ## c,a,d_ ## a)

38
#define _poly_monic(c,a)				ff_poly_monic(c,&d_ ## c,a,d_ ## a)

39
#define _poly_addto(c,a)				ff_poly_addto(c,&d_ ## c,a,d_ ## a)

40
#define _poly_add(c,a,b)				ff_poly_add(c,&d_ ## c,a,d_ ## a,b,d_ ## b)

41
#define _poly_sub(c,a,b)				ff_poly_sub(c,&d_ ## c,a,d_ ## a,b,d_ ## b)

42
#define _poly_mult(c,a,b)			ff_poly_mult(c,&d_ ## c,a,d_ ## a,b,d_ ## b)

43
#define _poly_div(q,r,a,b)			ff_poly_div(q,&d_ ## q,r,&d_ ## r,a,d_ ## a,b,d_ ## b)

44
#define _poly_mod(c,a,b)			ff_poly_mod(c,&d_ ## c,a,d_ ## a,b,d_ ## b)

45
#define _poly_gcd(c,a,b)				ff_poly_gcd(c,&d_ ## c,a,d_ ## a,b,d_ ## b)

46
#define _poly_gcdext(c,u,v,a,b)		ff_poly_gcdext(c,&d_ ## c,u,&d_ ## u, v,&d_ ## v,a,d_ ## a,b,d_ ## b)

47
#define _poly_expmod(c,a,e,b)		ff_poly_exp_mod(c,&d_ ## c,a,&d_ ## a,e,b,&d_ ## b)

48


49
int poly_expr_degree (char *str, int *ws);

50
void mpq_poly_weierstrass (mpq_t f[4], mpz_t W[5]);

51
int mpq_poly_expr (mpq_t f[], int maxd, char *expr);				// handles Weierstrass or standard form

52
int mpq_poly_standardize (mpq_t f[], int d);						// make d-1 coefficient zero

53
int mpq_poly_jinv_i (mpq_t j, long a[5]);

54


55
int mpz_poly_expr (mpz_t f[], int maxd, char *expr);

56
int mpz_poly_sprint (char *s, mpz_t f[], int d_f);

57
void mpz_poly_print (mpz_t f[], int d_f);

58
void mpz_poly_discriminant (mpz_t disc, mpz_t f[], int d);

59
void mpq_poly_discriminant (mpq_t disc, mpq_t f[], int d);

60
int ui_poly_expr (unsigned long f[], int maxd, char *expr);

61
int ui_poly_expr_mod_p (unsigned long f[], int maxd, char *expr, unsigned long p);

62
int i_poly_expr (long f[], int maxd, char *expr);

63
int ui_poly_sprint (char *s, unsigned long f[], int d_f);

64
void ui_poly_print (unsigned long f[], int d_f);

65
int i_poly_sprint (char *s, long f[], int d_f);

66
void i_poly_print (long f[], int d_f);

67


68
unsigned long i_poly_set_mpq (long f[], mpq_t F[], int d);			// sets f[i] to numberator of F[i] with common denominator and returns denominator or zero if overflow

69
void mpz_poly_set_mpq (mpz_t denom, mpz_t f[], mpq_t F[], int d);	// computes integer denom and integer poly f s.t. f/denom = F

70
int ff_poly_set_rational_mpz (ff_t f[], mpz_t F[], int d, mpz_t denom);

71
int ui_poly_set_rational_mpz_mod_p (unsigned long f[], mpz_t F[], int d, mpz_t denom, unsigned long p);

72


73
int ff_poly_expr (ff_t f[], int maxd, char *expr);

74
void ff_poly_print (ff_t f[], int d_f);

75
int ff_poly_sprint (char *s, ff_t f[], int d_f);

76


77
void ff_poly_eval (ff_t y[1], ff_t f[], int d, ff_t x[1]);

78
void ff_poly_twist_mpz (ff_t g[], mpz_t f[], int d);

79
void ff_poly_twist (ff_t g[], ff_t f[], int d);

80
int ff_poly_irreducible (ff_t f[], int d_f, int *pnroots);	// pnroots is the number of distinct roots

81
int ff_poly_factors (ff_t f[], int d_f);					// number of (not-necessarily distinct) irreducible factors

82
int ff_poly_roots (ff_t f[], int d_f);

83
void ff_poly_derivative (ff_t g[], int *pd_g, ff_t f[], int d_f);

84
void ff_poly_discriminant (ff_t disc[1], ff_t f[], int d);

85
void ff_poly_exp_mod (ff_t g[], int *pd_g, ff_t a[], int d_a, mpz_t e, ff_t f[], int d_f);

86
void ff_poly_gcd (ff_t g[], int *pd_g, ff_t a[], int d_a, ff_t b[], int d_b);

87
void ff_poly_gcd_red (ff_t g[], int *pd_g, ff_t a[], int d_a, ff_t b[], int d_b);

88
void ff_poly_gcdext (ff_t D[], int *pd_D, ff_t u[], int *pd_u, ff_t v[], int *pd_v, ff_t a[], int d_a, ff_t b[], int d_b);

89
void ff_poly_mod (ff_t g[], int *pd_g, ff_t a[], int d_a, ff_t f[], int d_f);

90
void ff_poly_div (ff_t q[], int *pd_q, ff_t r[], int *pd_r, ff_t a[], int d_a, ff_t b[], int d_b);

91
void ff_poly_neg (ff_t c[], int *pd_c, ff_t a[], int d_a);

92
void ff_poly_addto (ff_t c[], int *pd_c, ff_t a[], int d_a);

93
void ff_poly_add (ff_t c[], int *pd_c, ff_t a[], int d_a, ff_t b[], int d_b);

94
void ff_poly_sub (ff_t c[], int *pd_c, ff_t a[], int d_a, ff_t b[], int d_b);

95
void ff_poly_mult (ff_t c[], int *pd_c, ff_t a[], int d_a, ff_t b[], int d_b);

96
void ff_poly_monic (ff_t c[], int *pd_c, ff_t b[], int d_b);

97


98
int mpz_poly_bad_primes (unsigned long bad[], int maxbad, mpz_t f[], int d);

99
int mpq_poly_bad_primes (unsigned long bad[], int maxbad, mpq_t f[], int d);

100


101
void ff_depress_cubic (ff_t t[1], ff_t f[4]);					// puts monic f into the form x^3+ax+b via translation f(x-t)

102
void ff_depressed_cubic_resolvent (ff_t t[1], ff_t g[4], ff_t f[5]);	// forms cubic resolvent of depressed quartic and depresses it via translation t

103
int ff_poly_roots_d2 (ff_t r[2], ff_t f[3], int d_f);				// f may be quadratic or linear, needn't be monic

104
int _ff_poly_roots_d3 (ff_t r[3], ff_t f[4], ff_t *pd);				// f must be of the form x^3+ax+b, r may be null if only a count is desired

105
static inline int ff_poly_roots_d3 (ff_t r[3], ff_t f[4]) { return _ff_poly_roots_d3 (r, f, 0); }

106
int ff_old_poly_roots_d3 (ff_t r[3], ff_t f[4]);

107
int _ff_poly_roots_d4 (ff_t r[4], ff_t f[5], ff_t *pd);

108
static inline int ff_poly_roots_d4 (ff_t r[3], ff_t f[4]) { return _ff_poly_roots_d4 (r, f, 0); }

109
int ff_old_poly_roots_d4 (ff_t r[4], ff_t f[5]);

110
int ff_poly_g1_3tor (ff_t f[4]);								// f must be of the form x^3+ax+b

111
int ff_poly_g1_4tor (int *o, ff_t f[4], int flag8);				// f must be of the form x^3+ax+b (flag8 set indicates that Z/8Z should also be checked)

112
int ff_poly_g2_3tor (ff_t f[5]);								// f must be of the form x^5+ax+b

113
void ff_poly_xn_mod_d3 (ff_t g[3], unsigned long n, ff_t f[4]);	// computes x^n mod f=x^3+ax+b

114
void ff_poly_xn_mod_d4 (ff_t g[3], unsigned long n, ff_t f[5]);

115
void ff_poly_xpan_mod_d3 (ff_t g[3], ff_t a, unsigned long n, ff_t f[4]);

116
void ff_poly_xpan_mod_d4 (ff_t g[4], ff_t a, unsigned long n, ff_t f[5]);

117
void ff_poly_g2tor3_modpoly (ff_t g[41], ff_t f[6]);

118


119
int ff_poly_g1_2Sylow (ff_t f[4]);							// returns size of the 2-Sylow subgroup of the elliptic curve y^2=f(x)=x^3+f1x+f0, provided it is cyclic, returns -1 otherwise.

120


121
static inline void ff_poly_copy (ff_t b[], int *pd_b, ff_t a[], int d_a)

122
{

123
	register int i;

124
	

125
	for ( i = 0 ; i <= d_a ; i++ ) _ff_set(b[i], a[i]);

126
	*pd_b = d_a;

127
}

128


129
static inline int ff_poly_equal (ff_t a[], int d_a, ff_t b[], int d_b)

130
{

131
	register int i;

132
	

133
	if ( d_a != d_b ) return 0;

134
	for ( i = 0 ; i <= d_a ; i++ ) if ( ! _ff_equal(a[i],b[i]) ) return 0;

135
	return 1;

136
}

137


138
static inline void ff_poly_set_i (ff_t f[], long F[], int d) { register int i;  for ( i = 0 ; i <= d ; i++ ) _ff_set_i(f[i],F[i]); }

139


140
#endif

141


142