	.file	"1128651.c"
	.intel_syntax noprefix
	.text
	.section	.rodata
.LC0:
	.string	"the_stack_data/1128651.c"
.LC1:
	.string	"q > 0"
	.text
	.type	power, @function
power:
.LFB6:
	.cfi_startproc
	endbr64
	push	rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	mov	rbp, rsp
	.cfi_def_cfa_register 6
	sub	rsp, 32
	mov	DWORD PTR -20[rbp], edi
	mov	DWORD PTR -24[rbp], esi
	mov	DWORD PTR -28[rbp], edx
	cmp	DWORD PTR -28[rbp], 0
	jne	.L2
	lea	rcx, __PRETTY_FUNCTION__.4[rip]
	mov	edx, 33
	lea	rsi, .LC0[rip]
	lea	rdi, .LC1[rip]
	call	__assert_fail@PLT
.L2:
	mov	DWORD PTR -4[rbp], 1
	jmp	.L3
.L5:
	mov	eax, DWORD PTR -24[rbp]
	and	eax, 1
	test	eax, eax
	je	.L4
	mov	eax, DWORD PTR -4[rbp]
	imul	eax, DWORD PTR -20[rbp]
	mov	edx, 0
	div	DWORD PTR -28[rbp]
	mov	DWORD PTR -4[rbp], edx
.L4:
	shr	DWORD PTR -24[rbp]
	mov	eax, DWORD PTR -20[rbp]
	imul	eax, eax
	mov	edx, 0
	div	DWORD PTR -28[rbp]
	mov	DWORD PTR -20[rbp], edx
.L3:
	cmp	DWORD PTR -24[rbp], 0
	jne	.L5
	mov	eax, DWORD PTR -4[rbp]
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE6:
	.size	power, .-power
	.section	.rodata
	.align 8
.LC2:
	.string	"r1 == (int32_t) n * u1 + (int32_t) q * v1"
	.align 8
.LC3:
	.string	"r2 == (int32_t) n * u2 + (int32_t) q * v2"
.LC4:
	.string	"r1 >= 0"
	.align 8
.LC5:
	.string	"((((int32_t) n) * u1) % (int32_t) q) == 1"
	.text
	.type	inverse, @function
inverse:
.LFB7:
	.cfi_startproc
	endbr64
	push	rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	mov	rbp, rsp
	.cfi_def_cfa_register 6
	sub	rsp, 48
	mov	DWORD PTR -36[rbp], edi
	mov	DWORD PTR -40[rbp], esi
	mov	QWORD PTR -48[rbp], rdx
	mov	eax, DWORD PTR -36[rbp]
	mov	DWORD PTR -32[rbp], eax
	mov	DWORD PTR -24[rbp], 1
	mov	DWORD PTR -16[rbp], 0
	mov	eax, DWORD PTR -40[rbp]
	mov	DWORD PTR -28[rbp], eax
	mov	DWORD PTR -20[rbp], 0
	mov	DWORD PTR -12[rbp], 1
	jmp	.L8
.L12:
	mov	eax, DWORD PTR -36[rbp]
	imul	eax, DWORD PTR -24[rbp]
	mov	edx, eax
	mov	eax, DWORD PTR -40[rbp]
	imul	eax, DWORD PTR -16[rbp]
	add	eax, edx
	cmp	DWORD PTR -32[rbp], eax
	je	.L9
	lea	rcx, __PRETTY_FUNCTION__.3[rip]
	mov	edx, 58
	lea	rsi, .LC0[rip]
	lea	rdi, .LC2[rip]
	call	__assert_fail@PLT
.L9:
	mov	eax, DWORD PTR -36[rbp]
	imul	eax, DWORD PTR -20[rbp]
	mov	edx, eax
	mov	eax, DWORD PTR -40[rbp]
	imul	eax, DWORD PTR -12[rbp]
	add	eax, edx
	cmp	DWORD PTR -28[rbp], eax
	je	.L10
	lea	rcx, __PRETTY_FUNCTION__.3[rip]
	mov	edx, 59
	lea	rsi, .LC0[rip]
	lea	rdi, .LC3[rip]
	call	__assert_fail@PLT
.L10:
	cmp	DWORD PTR -32[rbp], 0
	jns	.L11
	lea	rcx, __PRETTY_FUNCTION__.3[rip]
	mov	edx, 60
	lea	rsi, .LC0[rip]
	lea	rdi, .LC4[rip]
	call	__assert_fail@PLT
.L11:
	mov	eax, DWORD PTR -32[rbp]
	cdq
	idiv	DWORD PTR -28[rbp]
	mov	DWORD PTR -8[rbp], eax
	mov	eax, DWORD PTR -32[rbp]
	mov	DWORD PTR -4[rbp], eax
	mov	eax, DWORD PTR -28[rbp]
	mov	DWORD PTR -32[rbp], eax
	mov	eax, DWORD PTR -8[rbp]
	imul	eax, DWORD PTR -28[rbp]
	mov	edx, eax
	mov	eax, DWORD PTR -4[rbp]
	sub	eax, edx
	mov	DWORD PTR -28[rbp], eax
	mov	eax, DWORD PTR -24[rbp]
	mov	DWORD PTR -4[rbp], eax
	mov	eax, DWORD PTR -20[rbp]
	mov	DWORD PTR -24[rbp], eax
	mov	eax, DWORD PTR -8[rbp]
	imul	eax, DWORD PTR -20[rbp]
	mov	edx, eax
	mov	eax, DWORD PTR -4[rbp]
	sub	eax, edx
	mov	DWORD PTR -20[rbp], eax
	mov	eax, DWORD PTR -16[rbp]
	mov	DWORD PTR -4[rbp], eax
	mov	eax, DWORD PTR -12[rbp]
	mov	DWORD PTR -16[rbp], eax
	mov	eax, DWORD PTR -8[rbp]
	imul	eax, DWORD PTR -12[rbp]
	mov	edx, eax
	mov	eax, DWORD PTR -4[rbp]
	sub	eax, edx
	mov	DWORD PTR -12[rbp], eax
.L8:
	cmp	DWORD PTR -28[rbp], 0
	jg	.L12
	cmp	DWORD PTR -32[rbp], 1
	jne	.L13
	mov	ecx, DWORD PTR -40[rbp]
	mov	eax, DWORD PTR -24[rbp]
	cdq
	idiv	ecx
	mov	DWORD PTR -24[rbp], edx
	cmp	DWORD PTR -24[rbp], 0
	jns	.L14
	mov	edx, DWORD PTR -24[rbp]
	mov	eax, DWORD PTR -40[rbp]
	add	eax, edx
	mov	DWORD PTR -24[rbp], eax
.L14:
	mov	eax, DWORD PTR -36[rbp]
	imul	eax, DWORD PTR -24[rbp]
	mov	ecx, DWORD PTR -40[rbp]
	cdq
	idiv	ecx
	mov	eax, edx
	cmp	eax, 1
	je	.L15
	lea	rcx, __PRETTY_FUNCTION__.3[rip]
	mov	edx, 72
	lea	rsi, .LC0[rip]
	lea	rdi, .LC5[rip]
	call	__assert_fail@PLT
.L15:
	mov	edx, DWORD PTR -24[rbp]
	mov	rax, QWORD PTR -48[rbp]
	mov	DWORD PTR [rax], edx
	mov	eax, 1
	jmp	.L16
.L13:
	mov	eax, 0
.L16:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE7:
	.size	inverse, .-inverse
	.type	find_k, @function
find_k:
.LFB8:
	.cfi_startproc
	endbr64
	push	rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	mov	rbp, rsp
	.cfi_def_cfa_register 6
	mov	DWORD PTR -20[rbp], edi
	mov	eax, DWORD PTR -20[rbp]
	sub	eax, 1
	mov	DWORD PTR -4[rbp], eax
	jmp	.L18
.L19:
	shr	DWORD PTR -4[rbp]
.L18:
	mov	eax, DWORD PTR -4[rbp]
	and	eax, 1
	test	eax, eax
	je	.L19
	mov	eax, DWORD PTR -4[rbp]
	pop	rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE8:
	.size	find_k, .-find_k
	.section	.rodata
.LC6:
	.string	"i == t+j"
.LC7:
	.string	"i < n"
	.text
	.type	build_shoup_red_table, @function
build_shoup_red_table:
.LFB9:
	.cfi_startproc
	endbr64
	push	rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	mov	rbp, rsp
	.cfi_def_cfa_register 6
	sub	rsp, 64
	mov	QWORD PTR -40[rbp], rdi
	mov	DWORD PTR -44[rbp], esi
	mov	DWORD PTR -48[rbp], edx
	mov	DWORD PTR -52[rbp], ecx
	mov	DWORD PTR -56[rbp], r8d
	mov	rax, QWORD PTR -40[rbp]
	mov	DWORD PTR [rax], 0
	mov	DWORD PTR -12[rbp], 1
	mov	DWORD PTR -20[rbp], 1
	jmp	.L22
.L27:
	mov	eax, DWORD PTR -56[rbp]
	mov	DWORD PTR -8[rbp], eax
	mov	eax, DWORD PTR -20[rbp]
	lea	esi, [rax+rax]
	mov	eax, DWORD PTR -44[rbp]
	mov	edx, 0
	div	esi
	mov	ecx, eax
	mov	edx, DWORD PTR -48[rbp]
	mov	eax, DWORD PTR -52[rbp]
	mov	esi, ecx
	mov	edi, eax
	call	power
	mov	DWORD PTR -4[rbp], eax
	mov	DWORD PTR -16[rbp], 0
	jmp	.L23
.L26:
	mov	edx, DWORD PTR -20[rbp]
	mov	eax, DWORD PTR -16[rbp]
	add	eax, edx
	cmp	DWORD PTR -12[rbp], eax
	je	.L24
	lea	rcx, __PRETTY_FUNCTION__.2[rip]
	mov	edx, 107
	lea	rsi, .LC0[rip]
	lea	rdi, .LC6[rip]
	call	__assert_fail@PLT
.L24:
	mov	eax, DWORD PTR -12[rbp]
	cmp	eax, DWORD PTR -44[rbp]
	jb	.L25
	lea	rcx, __PRETTY_FUNCTION__.2[rip]
	mov	edx, 108
	lea	rsi, .LC0[rip]
	lea	rdi, .LC7[rip]
	call	__assert_fail@PLT
.L25:
	mov	eax, DWORD PTR -12[rbp]
	lea	rdx, 0[0+rax*4]
	mov	rax, QWORD PTR -40[rbp]
	add	rdx, rax
	mov	eax, DWORD PTR -8[rbp]
	mov	DWORD PTR [rdx], eax
	add	DWORD PTR -12[rbp], 1
	mov	eax, DWORD PTR -8[rbp]
	imul	eax, DWORD PTR -4[rbp]
	mov	edx, 0
	div	DWORD PTR -48[rbp]
	mov	DWORD PTR -8[rbp], edx
	add	DWORD PTR -16[rbp], 1
.L23:
	mov	eax, DWORD PTR -16[rbp]
	cmp	eax, DWORD PTR -20[rbp]
	jb	.L26
	sal	DWORD PTR -20[rbp]
.L22:
	mov	eax, DWORD PTR -20[rbp]
	cmp	eax, DWORD PTR -44[rbp]
	jb	.L27
	nop
	nop
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE9:
	.size	build_shoup_red_table, .-build_shoup_red_table
	.section	.rodata
.LC8:
	.string	"x < q"
	.text
	.type	shift, @function
shift:
.LFB10:
	.cfi_startproc
	endbr64
	push	rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	mov	rbp, rsp
	.cfi_def_cfa_register 6
	sub	rsp, 16
	mov	DWORD PTR -4[rbp], edi
	mov	DWORD PTR -8[rbp], esi
	mov	eax, DWORD PTR -4[rbp]
	cmp	eax, DWORD PTR -8[rbp]
	jb	.L29
	lea	rcx, __PRETTY_FUNCTION__.1[rip]
	mov	edx, 121
	lea	rsi, .LC0[rip]
	lea	rdi, .LC8[rip]
	call	__assert_fail@PLT
.L29:
	mov	eax, DWORD PTR -8[rbp]
	shr	eax
	cmp	DWORD PTR -4[rbp], eax
	jbe	.L30
	mov	eax, DWORD PTR -4[rbp]
	sub	eax, DWORD PTR -8[rbp]
	jmp	.L32
.L30:
	mov	eax, DWORD PTR -4[rbp]
.L32:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE10:
	.size	shift, .-shift
	.section	.rodata
	.align 8
.LC9:
	.string	"\nconst int32_t %s%u_%u[%u] = {\n"
.LC10:
	.string	"   "
.LC11:
	.string	" %5d,"
.LC12:
	.string	" %5u,"
.LC13:
	.string	"};\n\n"
	.text
	.type	print_table, @function
print_table:
.LFB11:
	.cfi_startproc
	endbr64
	push	rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	mov	rbp, rsp
	.cfi_def_cfa_register 6
	sub	rsp, 64
	mov	QWORD PTR -24[rbp], rdi
	mov	QWORD PTR -32[rbp], rsi
	mov	QWORD PTR -40[rbp], rdx
	mov	DWORD PTR -44[rbp], ecx
	mov	DWORD PTR -48[rbp], r8d
	mov	eax, r9d
	mov	BYTE PTR -52[rbp], al
	mov	DWORD PTR -4[rbp], 0
	mov	edi, DWORD PTR -44[rbp]
	mov	esi, DWORD PTR -48[rbp]
	mov	ecx, DWORD PTR -44[rbp]
	mov	rdx, QWORD PTR -32[rbp]
	mov	rax, QWORD PTR -24[rbp]
	mov	r9d, edi
	mov	r8d, esi
	lea	rsi, .LC9[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	DWORD PTR -8[rbp], 0
	jmp	.L34
.L39:
	cmp	DWORD PTR -4[rbp], 0
	jne	.L35
	mov	rax, QWORD PTR -24[rbp]
	mov	rcx, rax
	mov	edx, 3
	mov	esi, 1
	lea	rdi, .LC10[rip]
	call	fwrite@PLT
.L35:
	cmp	BYTE PTR -52[rbp], 0
	je	.L36
	mov	eax, DWORD PTR -8[rbp]
	lea	rdx, 0[0+rax*4]
	mov	rax, QWORD PTR -40[rbp]
	add	rax, rdx
	mov	eax, DWORD PTR [rax]
	mov	edx, DWORD PTR -48[rbp]
	mov	esi, edx
	mov	edi, eax
	call	shift
	mov	edx, eax
	mov	rax, QWORD PTR -24[rbp]
	lea	rsi, .LC11[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	jmp	.L37
.L36:
	mov	eax, DWORD PTR -8[rbp]
	lea	rdx, 0[0+rax*4]
	mov	rax, QWORD PTR -40[rbp]
	add	rax, rdx
	mov	edx, DWORD PTR [rax]
	mov	rax, QWORD PTR -24[rbp]
	lea	rsi, .LC12[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
.L37:
	add	DWORD PTR -4[rbp], 1
	cmp	DWORD PTR -4[rbp], 8
	jne	.L38
	mov	rax, QWORD PTR -24[rbp]
	mov	rsi, rax
	mov	edi, 10
	call	fputc@PLT
	mov	DWORD PTR -4[rbp], 0
.L38:
	add	DWORD PTR -8[rbp], 1
.L34:
	mov	eax, DWORD PTR -8[rbp]
	cmp	eax, DWORD PTR -44[rbp]
	jb	.L39
	cmp	DWORD PTR -4[rbp], 0
	je	.L40
	mov	rax, QWORD PTR -24[rbp]
	mov	rsi, rax
	mov	edi, 10
	call	fputc@PLT
.L40:
	mov	rax, QWORD PTR -24[rbp]
	mov	rcx, rax
	mov	edx, 4
	mov	esi, 1
	lea	rdi, .LC13[rip]
	call	fwrite@PLT
	nop
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE11:
	.size	print_table, .-print_table
	.section	.rodata
	.align 8
.LC14:
	.string	"Usage: %s <modulus> <size> <psi>\n"
	.align 8
.LC15:
	.string	"Invalid modulus %s: must be at least 2\n"
	.align 8
.LC16:
	.string	"The modulus is too large: max = %u\n"
	.align 8
.LC17:
	.string	"Extracted k = %u, not between 1 and q-1\n"
	.align 8
.LC18:
	.string	"Invalid size %s: must be at least 2\n"
	.align 8
.LC19:
	.string	"The size is too large: max = %u\n"
.LC20:
	.string	"psi must be between 2 and %u\n"
	.align 8
.LC21:
	.string	"invalid psi: %u is not an n-th root of -1  (%u^n = %u)\n"
.LC22:
	.string	"power(phi, n, q) == 1"
	.align 8
.LC23:
	.string	"invalid psi: psi^2 is not a primitive n-th root of unity (psi^2 = %u)\n"
.LC24:
	.string	"             (psi^2)^u = 1\n"
	.align 8
.LC25:
	.string	"invalid parameters: n = %u is not invertible modulo %u\n"
	.align 8
.LC26:
	.string	"invalid parameters: k = %u is not invertible modulo %u\n"
.LC27:
	.string	"Parameters\n"
.LC28:
	.string	"q = %u\n"
.LC29:
	.string	"k = %u\n"
.LC30:
	.string	"n = %u\n"
.LC31:
	.string	"psi = %u\n"
.LC32:
	.string	"psi^2 = %u\n"
.LC33:
	.string	"n^(-1) = %u\n"
.LC34:
	.string	"k^(-1) = %u\n"
	.align 8
.LC35:
	.string	"failed to allocate table of size %u\n"
.LC36:
	.string	"shoup_red_ntt"
.LC37:
	.string	"shoup_sred_ntt"
	.text
	.globl	main
	.type	main, @function
main:
.LFB12:
	.cfi_startproc
	endbr64
	push	rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	mov	rbp, rsp
	.cfi_def_cfa_register 6
	sub	rsp, 80
	mov	DWORD PTR -68[rbp], edi
	mov	QWORD PTR -80[rbp], rsi
	mov	rax, QWORD PTR fs:40
	mov	QWORD PTR -8[rbp], rax
	xor	eax, eax
	cmp	DWORD PTR -68[rbp], 4
	je	.L42
	mov	rax, QWORD PTR -80[rbp]
	mov	rdx, QWORD PTR [rax]
	mov	rax, QWORD PTR stderr[rip]
	lea	rsi, .LC14[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	edi, 1
	call	exit@PLT
.L42:
	mov	rax, QWORD PTR -80[rbp]
	add	rax, 8
	mov	rax, QWORD PTR [rax]
	mov	rdi, rax
	call	atol@PLT
	mov	QWORD PTR -24[rbp], rax
	cmp	QWORD PTR -24[rbp], 1
	jg	.L43
	mov	rax, QWORD PTR -80[rbp]
	add	rax, 8
	mov	rdx, QWORD PTR [rax]
	mov	rax, QWORD PTR stderr[rip]
	lea	rsi, .LC15[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	edi, 1
	call	exit@PLT
.L43:
	cmp	QWORD PTR -24[rbp], 65534
	jle	.L44
	mov	rax, QWORD PTR stderr[rip]
	mov	edx, 65535
	lea	rsi, .LC16[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	edi, 1
	call	exit@PLT
.L44:
	mov	rax, QWORD PTR -24[rbp]
	mov	DWORD PTR -44[rbp], eax
	mov	eax, DWORD PTR -44[rbp]
	mov	edi, eax
	call	find_k
	mov	DWORD PTR -40[rbp], eax
	cmp	DWORD PTR -40[rbp], 0
	je	.L45
	mov	eax, DWORD PTR -40[rbp]
	cmp	eax, DWORD PTR -44[rbp]
	jb	.L46
.L45:
	mov	rax, QWORD PTR stderr[rip]
	mov	edx, DWORD PTR -40[rbp]
	lea	rsi, .LC17[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	edi, 1
	call	exit@PLT
.L46:
	mov	rax, QWORD PTR -80[rbp]
	add	rax, 16
	mov	rax, QWORD PTR [rax]
	mov	rdi, rax
	call	atol@PLT
	mov	QWORD PTR -24[rbp], rax
	cmp	QWORD PTR -24[rbp], 1
	jg	.L47
	mov	rax, QWORD PTR -80[rbp]
	add	rax, 16
	mov	rdx, QWORD PTR [rax]
	mov	rax, QWORD PTR stderr[rip]
	lea	rsi, .LC18[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	edi, 1
	call	exit@PLT
.L47:
	cmp	QWORD PTR -24[rbp], 99999
	jle	.L48
	mov	rax, QWORD PTR stderr[rip]
	mov	edx, 100000
	lea	rsi, .LC19[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	edi, 1
	call	exit@PLT
.L48:
	mov	rax, QWORD PTR -24[rbp]
	mov	DWORD PTR -36[rbp], eax
	mov	rax, QWORD PTR -80[rbp]
	add	rax, 24
	mov	rax, QWORD PTR [rax]
	mov	rdi, rax
	call	atol@PLT
	mov	QWORD PTR -24[rbp], rax
	cmp	QWORD PTR -24[rbp], 1
	jle	.L49
	mov	eax, DWORD PTR -44[rbp]
	cmp	QWORD PTR -24[rbp], rax
	jl	.L50
.L49:
	mov	eax, DWORD PTR -44[rbp]
	lea	edx, -1[rax]
	mov	rax, QWORD PTR stderr[rip]
	lea	rsi, .LC20[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	edi, 1
	call	exit@PLT
.L50:
	mov	rax, QWORD PTR -24[rbp]
	mov	DWORD PTR -32[rbp], eax
	mov	eax, DWORD PTR -32[rbp]
	imul	eax, eax
	mov	edx, 0
	div	DWORD PTR -44[rbp]
	mov	DWORD PTR -28[rbp], edx
	mov	edx, DWORD PTR -44[rbp]
	mov	ecx, DWORD PTR -36[rbp]
	mov	eax, DWORD PTR -32[rbp]
	mov	esi, ecx
	mov	edi, eax
	call	power
	mov	DWORD PTR -48[rbp], eax
	mov	eax, DWORD PTR -44[rbp]
	sub	eax, 1
	cmp	DWORD PTR -48[rbp], eax
	je	.L51
	mov	rax, QWORD PTR stderr[rip]
	mov	esi, DWORD PTR -48[rbp]
	mov	ecx, DWORD PTR -32[rbp]
	mov	edx, DWORD PTR -32[rbp]
	mov	r8d, esi
	lea	rsi, .LC21[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	edi, 1
	call	exit@PLT
.L51:
	mov	edx, DWORD PTR -44[rbp]
	mov	ecx, DWORD PTR -36[rbp]
	mov	eax, DWORD PTR -28[rbp]
	mov	esi, ecx
	mov	edi, eax
	call	power
	cmp	eax, 1
	je	.L52
	lea	rcx, __PRETTY_FUNCTION__.0[rip]
	mov	edx, 206
	lea	rsi, .LC0[rip]
	lea	rdi, .LC22[rip]
	call	__assert_fail@PLT
.L52:
	mov	DWORD PTR -48[rbp], 1
	jmp	.L53
.L55:
	mov	edx, DWORD PTR -44[rbp]
	mov	ecx, DWORD PTR -48[rbp]
	mov	eax, DWORD PTR -32[rbp]
	mov	esi, ecx
	mov	edi, eax
	call	power
	cmp	eax, 1
	jne	.L54
	mov	rax, QWORD PTR stderr[rip]
	mov	edx, DWORD PTR -28[rbp]
	lea	rsi, .LC23[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	rax, QWORD PTR stderr[rip]
	mov	rcx, rax
	mov	edx, 27
	mov	esi, 1
	lea	rdi, .LC24[rip]
	call	fwrite@PLT
	mov	edi, 1
	call	exit@PLT
.L54:
	add	DWORD PTR -48[rbp], 1
.L53:
	mov	eax, DWORD PTR -48[rbp]
	cmp	eax, DWORD PTR -36[rbp]
	jb	.L55
	lea	rdx, -56[rbp]
	mov	ecx, DWORD PTR -44[rbp]
	mov	eax, DWORD PTR -36[rbp]
	mov	esi, ecx
	mov	edi, eax
	call	inverse
	xor	eax, 1
	test	al, al
	je	.L56
	mov	rax, QWORD PTR stderr[rip]
	mov	ecx, DWORD PTR -44[rbp]
	mov	edx, DWORD PTR -36[rbp]
	lea	rsi, .LC25[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	edi, 1
	call	exit@PLT
.L56:
	lea	rdx, -52[rbp]
	mov	ecx, DWORD PTR -44[rbp]
	mov	eax, DWORD PTR -40[rbp]
	mov	esi, ecx
	mov	edi, eax
	call	inverse
	xor	eax, 1
	test	al, al
	je	.L57
	mov	rax, QWORD PTR stderr[rip]
	mov	ecx, DWORD PTR -44[rbp]
	mov	edx, DWORD PTR -36[rbp]
	lea	rsi, .LC26[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	edi, 1
	call	exit@PLT
.L57:
	mov	rax, QWORD PTR stderr[rip]
	mov	rcx, rax
	mov	edx, 11
	mov	esi, 1
	lea	rdi, .LC27[rip]
	call	fwrite@PLT
	mov	rax, QWORD PTR stderr[rip]
	mov	edx, DWORD PTR -44[rbp]
	lea	rsi, .LC28[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	rax, QWORD PTR stderr[rip]
	mov	edx, DWORD PTR -40[rbp]
	lea	rsi, .LC29[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	rax, QWORD PTR stderr[rip]
	mov	edx, DWORD PTR -36[rbp]
	lea	rsi, .LC30[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	rax, QWORD PTR stderr[rip]
	mov	edx, DWORD PTR -32[rbp]
	lea	rsi, .LC31[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	rax, QWORD PTR stderr[rip]
	mov	edx, DWORD PTR -28[rbp]
	lea	rsi, .LC32[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	edx, DWORD PTR -56[rbp]
	mov	rax, QWORD PTR stderr[rip]
	lea	rsi, .LC33[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	edx, DWORD PTR -52[rbp]
	mov	rax, QWORD PTR stderr[rip]
	lea	rsi, .LC34[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	eax, DWORD PTR -36[rbp]
	sal	rax, 2
	mov	rdi, rax
	call	malloc@PLT
	mov	QWORD PTR -16[rbp], rax
	cmp	QWORD PTR -16[rbp], 0
	jne	.L58
	mov	rax, QWORD PTR stderr[rip]
	mov	edx, DWORD PTR -36[rbp]
	lea	rsi, .LC35[rip]
	mov	rdi, rax
	mov	eax, 0
	call	fprintf@PLT
	mov	edi, 1
	call	exit@PLT
.L58:
	mov	edi, DWORD PTR -52[rbp]
	mov	ecx, DWORD PTR -28[rbp]
	mov	edx, DWORD PTR -44[rbp]
	mov	esi, DWORD PTR -36[rbp]
	mov	rax, QWORD PTR -16[rbp]
	mov	r8d, edi
	mov	rdi, rax
	call	build_shoup_red_table
	mov	rax, QWORD PTR stdout[rip]
	mov	esi, DWORD PTR -44[rbp]
	mov	ecx, DWORD PTR -36[rbp]
	mov	rdx, QWORD PTR -16[rbp]
	mov	r9d, 0
	mov	r8d, esi
	lea	rsi, .LC36[rip]
	mov	rdi, rax
	call	print_table
	mov	rax, QWORD PTR stdout[rip]
	mov	esi, DWORD PTR -44[rbp]
	mov	ecx, DWORD PTR -36[rbp]
	mov	rdx, QWORD PTR -16[rbp]
	mov	r9d, 1
	mov	r8d, esi
	lea	rsi, .LC37[rip]
	mov	rdi, rax
	call	print_table
	mov	rax, QWORD PTR -16[rbp]
	mov	rdi, rax
	call	free@PLT
	mov	eax, 0
	mov	rcx, QWORD PTR -8[rbp]
	sub	rcx, QWORD PTR fs:40
	je	.L60
	call	__stack_chk_fail@PLT
.L60:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE12:
	.size	main, .-main
	.section	.rodata
	.type	__PRETTY_FUNCTION__.4, @object
	.size	__PRETTY_FUNCTION__.4, 6
__PRETTY_FUNCTION__.4:
	.string	"power"
	.align 8
	.type	__PRETTY_FUNCTION__.3, @object
	.size	__PRETTY_FUNCTION__.3, 8
__PRETTY_FUNCTION__.3:
	.string	"inverse"
	.align 16
	.type	__PRETTY_FUNCTION__.2, @object
	.size	__PRETTY_FUNCTION__.2, 22
__PRETTY_FUNCTION__.2:
	.string	"build_shoup_red_table"
	.type	__PRETTY_FUNCTION__.1, @object
	.size	__PRETTY_FUNCTION__.1, 6
__PRETTY_FUNCTION__.1:
	.string	"shift"
	.type	__PRETTY_FUNCTION__.0, @object
	.size	__PRETTY_FUNCTION__.0, 5
__PRETTY_FUNCTION__.0:
	.string	"main"
	.ident	"GCC: (Ubuntu 10.5.0-1ubuntu1~20.04) 10.5.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	 1f - 0f
	.long	 4f - 1f
	.long	 5
0:
	.string	 "GNU"
1:
	.align 8
	.long	 0xc0000002
	.long	 3f - 2f
2:
	.long	 0x3
3:
	.align 8
4:

	.arch armv5t
	.eabi_attribute 20, 1
	.eabi_attribute 21, 1
	.eabi_attribute 23, 3
	.eabi_attribute 24, 1
	.eabi_attribute 25, 1
	.eabi_attribute 26, 2
	.eabi_attribute 30, 6
	.eabi_attribute 34, 0
	.eabi_attribute 18, 4
	.file	"1128651.c"
	.text
	.section	.rodata
	.align	2
.LC0:
	.ascii	"the_stack_data/1128651.c\000"
	.align	2
.LC1:
	.ascii	"q > 0\000"
	.global	__aeabi_uidivmod
	.text
	.align	2
	.syntax unified
	.arm
	.fpu softvfp
	.type	power, %function
power:
	@ args = 0, pretend = 0, frame = 24
	@ frame_needed = 1, uses_anonymous_args = 0
	push	{fp, lr}
	add	fp, sp, #4
	sub	sp, sp, #24
	str	r0, [fp, #-16]
	str	r1, [fp, #-20]
	str	r2, [fp, #-24]
	ldr	r3, [fp, #-24]
	cmp	r3, #0
	bne	.L2
	ldr	r3, .L7
	mov	r2, #33
	ldr	r1, .L7+4
	ldr	r0, .L7+8
	bl	__assert_fail
.L2:
	mov	r3, #1
	str	r3, [fp, #-8]
	b	.L3
.L5:
	ldr	r3, [fp, #-20]
	and	r3, r3, #1
	cmp	r3, #0
	beq	.L4
	ldr	r3, [fp, #-8]
	ldr	r2, [fp, #-16]
	mul	r3, r2, r3
	ldr	r1, [fp, #-24]
	mov	r0, r3
	bl	__aeabi_uidivmod
	mov	r3, r1
	str	r3, [fp, #-8]
.L4:
	ldr	r3, [fp, #-20]
	lsr	r3, r3, #1
	str	r3, [fp, #-20]
	ldr	r3, [fp, #-16]
	mov	r2, r3
	mul	r2, r3, r2
	mov	r3, r2
	ldr	r1, [fp, #-24]
	mov	r0, r3
	bl	__aeabi_uidivmod
	mov	r3, r1
	str	r3, [fp, #-16]
.L3:
	ldr	r3, [fp, #-20]
	cmp	r3, #0
	bne	.L5
	ldr	r3, [fp, #-8]
	mov	r0, r3
	sub	sp, fp, #4
	@ sp needed
	pop	{fp, pc}
.L8:
	.align	2
.L7:
	.word	__PRETTY_FUNCTION__.5185
	.word	.LC0
	.word	.LC1
	.size	power, .-power
	.section	.rodata
	.align	2
.LC2:
	.ascii	"r1 == (int32_t) n * u1 + (int32_t) q * v1\000"
	.align	2
.LC3:
	.ascii	"r2 == (int32_t) n * u2 + (int32_t) q * v2\000"
	.align	2
.LC4:
	.ascii	"r1 >= 0\000"
	.global	__aeabi_idiv
	.global	__aeabi_idivmod
	.align	2
.LC5:
	.ascii	"((((int32_t) n) * u1) % (int32_t) q) == 1\000"
	.text
	.align	2
	.syntax unified
	.arm
	.fpu softvfp
	.type	inverse, %function
inverse:
	@ args = 0, pretend = 0, frame = 48
	@ frame_needed = 1, uses_anonymous_args = 0
	push	{fp, lr}
	add	fp, sp, #4
	sub	sp, sp, #48
	str	r0, [fp, #-40]
	str	r1, [fp, #-44]
	str	r2, [fp, #-48]
	ldr	r3, [fp, #-40]
	str	r3, [fp, #-36]
	mov	r3, #1
	str	r3, [fp, #-28]
	mov	r3, #0
	str	r3, [fp, #-20]
	ldr	r3, [fp, #-44]
	str	r3, [fp, #-32]
	mov	r3, #0
	str	r3, [fp, #-24]
	mov	r3, #1
	str	r3, [fp, #-16]
	b	.L10
.L14:
	ldr	r3, [fp, #-40]
	ldr	r2, [fp, #-28]
	mul	r2, r3, r2
	ldr	r3, [fp, #-44]
	ldr	r1, [fp, #-20]
	mul	r3, r1, r3
	add	r3, r2, r3
	ldr	r2, [fp, #-36]
	cmp	r2, r3
	beq	.L11
	ldr	r3, .L19
	mov	r2, #58
	ldr	r1, .L19+4
	ldr	r0, .L19+8
	bl	__assert_fail
.L11:
	ldr	r3, [fp, #-40]
	ldr	r2, [fp, #-24]
	mul	r2, r3, r2
	ldr	r3, [fp, #-44]
	ldr	r1, [fp, #-16]
	mul	r3, r1, r3
	add	r3, r2, r3
	ldr	r2, [fp, #-32]
	cmp	r2, r3
	beq	.L12
	ldr	r3, .L19
	mov	r2, #59
	ldr	r1, .L19+4
	ldr	r0, .L19+12
	bl	__assert_fail
.L12:
	ldr	r3, [fp, #-36]
	cmp	r3, #0
	bge	.L13
	ldr	r3, .L19
	mov	r2, #60
	ldr	r1, .L19+4
	ldr	r0, .L19+16
	bl	__assert_fail
.L13:
	ldr	r1, [fp, #-32]
	ldr	r0, [fp, #-36]
	bl	__aeabi_idiv
	mov	r3, r0
	str	r3, [fp, #-12]
	ldr	r3, [fp, #-36]
	str	r3, [fp, #-8]
	ldr	r3, [fp, #-32]
	str	r3, [fp, #-36]
	ldr	r3, [fp, #-12]
	ldr	r2, [fp, #-32]
	mul	r3, r2, r3
	ldr	r2, [fp, #-8]
	sub	r3, r2, r3
	str	r3, [fp, #-32]
	ldr	r3, [fp, #-28]
	str	r3, [fp, #-8]
	ldr	r3, [fp, #-24]
	str	r3, [fp, #-28]
	ldr	r3, [fp, #-12]
	ldr	r2, [fp, #-24]
	mul	r3, r2, r3
	ldr	r2, [fp, #-8]
	sub	r3, r2, r3
	str	r3, [fp, #-24]
	ldr	r3, [fp, #-20]
	str	r3, [fp, #-8]
	ldr	r3, [fp, #-16]
	str	r3, [fp, #-20]
	ldr	r3, [fp, #-12]
	ldr	r2, [fp, #-16]
	mul	r3, r2, r3
	ldr	r2, [fp, #-8]
	sub	r3, r2, r3
	str	r3, [fp, #-16]
.L10:
	ldr	r3, [fp, #-32]
	cmp	r3, #0
	bgt	.L14
	ldr	r3, [fp, #-36]
	cmp	r3, #1
	bne	.L15
	ldr	r2, [fp, #-44]
	ldr	r3, [fp, #-28]
	mov	r1, r2
	mov	r0, r3
	bl	__aeabi_idivmod
	mov	r3, r1
	str	r3, [fp, #-28]
	ldr	r3, [fp, #-28]
	cmp	r3, #0
	bge	.L16
	ldr	r2, [fp, #-28]
	ldr	r3, [fp, #-44]
	add	r3, r2, r3
	str	r3, [fp, #-28]
.L16:
	ldr	r3, [fp, #-40]
	ldr	r2, [fp, #-28]
	mul	r3, r2, r3
	ldr	r2, [fp, #-44]
	mov	r1, r2
	mov	r0, r3
	bl	__aeabi_idivmod
	mov	r3, r1
	cmp	r3, #1
	beq	.L17
	ldr	r3, .L19
	mov	r2, #72
	ldr	r1, .L19+4
	ldr	r0, .L19+20
	bl	__assert_fail
.L17:
	ldr	r2, [fp, #-28]
	ldr	r3, [fp, #-48]
	str	r2, [r3]
	mov	r3, #1
	b	.L18
.L15:
	mov	r3, #0
.L18:
	mov	r0, r3
	sub	sp, fp, #4
	@ sp needed
	pop	{fp, pc}
.L20:
	.align	2
.L19:
	.word	__PRETTY_FUNCTION__.5202
	.word	.LC0
	.word	.LC2
	.word	.LC3
	.word	.LC4
	.word	.LC5
	.size	inverse, .-inverse
	.align	2
	.syntax unified
	.arm
	.fpu softvfp
	.type	find_k, %function
find_k:
	@ args = 0, pretend = 0, frame = 16
	@ frame_needed = 1, uses_anonymous_args = 0
	@ link register save eliminated.
	str	fp, [sp, #-4]!
	add	fp, sp, #0
	sub	sp, sp, #20
	str	r0, [fp, #-16]
	ldr	r3, [fp, #-16]
	sub	r3, r3, #1
	str	r3, [fp, #-8]
	b	.L22
.L23:
	ldr	r3, [fp, #-8]
	lsr	r3, r3, #1
	str	r3, [fp, #-8]
.L22:
	ldr	r3, [fp, #-8]
	and	r3, r3, #1
	cmp	r3, #0
	beq	.L23
	ldr	r3, [fp, #-8]
	mov	r0, r3
	add	sp, fp, #0
	@ sp needed
	ldr	fp, [sp], #4
	bx	lr
	.size	find_k, .-find_k
	.global	__aeabi_uidiv
	.section	.rodata
	.align	2
.LC6:
	.ascii	"i == t+j\000"
	.align	2
.LC7:
	.ascii	"i < n\000"
	.text
	.align	2
	.syntax unified
	.arm
	.fpu softvfp
	.type	build_shoup_red_table, %function
build_shoup_red_table:
	@ args = 4, pretend = 0, frame = 40
	@ frame_needed = 1, uses_anonymous_args = 0
	push	{fp, lr}
	add	fp, sp, #4
	sub	sp, sp, #40
	str	r0, [fp, #-32]
	str	r1, [fp, #-36]
	str	r2, [fp, #-40]
	str	r3, [fp, #-44]
	ldr	r3, [fp, #-32]
	mov	r2, #0
	str	r2, [r3]
	mov	r3, #1
	str	r3, [fp, #-16]
	mov	r3, #1
	str	r3, [fp, #-24]
	b	.L26
.L31:
	ldr	r3, [fp, #4]
	str	r3, [fp, #-12]
	ldr	r3, [fp, #-24]
	lsl	r3, r3, #1
	mov	r1, r3
	ldr	r0, [fp, #-36]
	bl	__aeabi_uidiv
	mov	r3, r0
	ldr	r2, [fp, #-40]
	mov	r1, r3
	ldr	r0, [fp, #-44]
	bl	power
	str	r0, [fp, #-8]
	mov	r3, #0
	str	r3, [fp, #-20]
	b	.L27
.L30:
	ldr	r2, [fp, #-24]
	ldr	r3, [fp, #-20]
	add	r3, r2, r3
	ldr	r2, [fp, #-16]
	cmp	r2, r3
	beq	.L28
	ldr	r3, .L32
	mov	r2, #107
	ldr	r1, .L32+4
	ldr	r0, .L32+8
	bl	__assert_fail
.L28:
	ldr	r2, [fp, #-16]
	ldr	r3, [fp, #-36]
	cmp	r2, r3
	bcc	.L29
	ldr	r3, .L32
	mov	r2, #108
	ldr	r1, .L32+4
	ldr	r0, .L32+12
	bl	__assert_fail
.L29:
	ldr	r3, [fp, #-16]
	lsl	r3, r3, #2
	ldr	r2, [fp, #-32]
	add	r3, r2, r3
	ldr	r2, [fp, #-12]
	str	r2, [r3]
	ldr	r3, [fp, #-16]
	add	r3, r3, #1
	str	r3, [fp, #-16]
	ldr	r3, [fp, #-12]
	ldr	r2, [fp, #-8]
	mul	r3, r2, r3
	ldr	r1, [fp, #-40]
	mov	r0, r3
	bl	__aeabi_uidivmod
	mov	r3, r1
	str	r3, [fp, #-12]
	ldr	r3, [fp, #-20]
	add	r3, r3, #1
	str	r3, [fp, #-20]
.L27:
	ldr	r2, [fp, #-20]
	ldr	r3, [fp, #-24]
	cmp	r2, r3
	bcc	.L30
	ldr	r3, [fp, #-24]
	lsl	r3, r3, #1
	str	r3, [fp, #-24]
.L26:
	ldr	r2, [fp, #-24]
	ldr	r3, [fp, #-36]
	cmp	r2, r3
	bcc	.L31
	nop
	nop
	sub	sp, fp, #4
	@ sp needed
	pop	{fp, pc}
.L33:
	.align	2
.L32:
	.word	__PRETTY_FUNCTION__.5225
	.word	.LC0
	.word	.LC6
	.word	.LC7
	.size	build_shoup_red_table, .-build_shoup_red_table
	.section	.rodata
	.align	2
.LC8:
	.ascii	"x < q\000"
	.text
	.align	2
	.syntax unified
	.arm
	.fpu softvfp
	.type	shift, %function
shift:
	@ args = 0, pretend = 0, frame = 8
	@ frame_needed = 1, uses_anonymous_args = 0
	push	{fp, lr}
	add	fp, sp, #4
	sub	sp, sp, #8
	str	r0, [fp, #-8]
	str	r1, [fp, #-12]
	ldr	r2, [fp, #-8]
	ldr	r3, [fp, #-12]
	cmp	r2, r3
	bcc	.L35
	ldr	r3, .L39
	mov	r2, #121
	ldr	r1, .L39+4
	ldr	r0, .L39+8
	bl	__assert_fail
.L35:
	ldr	r3, [fp, #-12]
	lsr	r3, r3, #1
	ldr	r2, [fp, #-8]
	cmp	r2, r3
	bls	.L36
	ldr	r2, [fp, #-8]
	ldr	r3, [fp, #-12]
	sub	r3, r2, r3
	b	.L38
.L36:
	ldr	r3, [fp, #-8]
.L38:
	mov	r0, r3
	sub	sp, fp, #4
	@ sp needed
	pop	{fp, pc}
.L40:
	.align	2
.L39:
	.word	__PRETTY_FUNCTION__.5236
	.word	.LC0
	.word	.LC8
	.size	shift, .-shift
	.section	.rodata
	.align	2
.LC9:
	.ascii	"\012const int32_t %s%u_%u[%u] = {\012\000"
	.align	2
.LC10:
	.ascii	"   \000"
	.align	2
.LC11:
	.ascii	" %5d,\000"
	.align	2
.LC12:
	.ascii	" %5u,\000"
	.align	2
.LC13:
	.ascii	"};\012\012\000"
	.text
	.align	2
	.syntax unified
	.arm
	.fpu softvfp
	.type	print_table, %function
print_table:
	@ args = 8, pretend = 0, frame = 24
	@ frame_needed = 1, uses_anonymous_args = 0
	push	{fp, lr}
	add	fp, sp, #4
	sub	sp, sp, #32
	str	r0, [fp, #-16]
	str	r1, [fp, #-20]
	str	r2, [fp, #-24]
	str	r3, [fp, #-28]
	mov	r3, #0
	str	r3, [fp, #-8]
	ldr	r3, [fp, #-28]
	str	r3, [sp, #4]
	ldr	r3, [fp, #4]
	str	r3, [sp]
	ldr	r3, [fp, #-28]
	ldr	r2, [fp, #-20]
	ldr	r1, .L49
	ldr	r0, [fp, #-16]
	bl	fprintf
	mov	r3, #0
	str	r3, [fp, #-12]
	b	.L42
.L47:
	ldr	r3, [fp, #-8]
	cmp	r3, #0
	bne	.L43
	ldr	r3, [fp, #-16]
	mov	r2, #3
	mov	r1, #1
	ldr	r0, .L49+4
	bl	fwrite
.L43:
	ldrb	r3, [fp, #8]	@ zero_extendqisi2
	cmp	r3, #0
	beq	.L44
	ldr	r3, [fp, #-12]
	lsl	r3, r3, #2
	ldr	r2, [fp, #-24]
	add	r3, r2, r3
	ldr	r3, [r3]
	ldr	r1, [fp, #4]
	mov	r0, r3
	bl	shift
	mov	r3, r0
	mov	r2, r3
	ldr	r1, .L49+8
	ldr	r0, [fp, #-16]
	bl	fprintf
	b	.L45
.L44:
	ldr	r3, [fp, #-12]
	lsl	r3, r3, #2
	ldr	r2, [fp, #-24]
	add	r3, r2, r3
	ldr	r3, [r3]
	mov	r2, r3
	ldr	r1, .L49+12
	ldr	r0, [fp, #-16]
	bl	fprintf
.L45:
	ldr	r3, [fp, #-8]
	add	r3, r3, #1
	str	r3, [fp, #-8]
	ldr	r3, [fp, #-8]
	cmp	r3, #8
	bne	.L46
	ldr	r1, [fp, #-16]
	mov	r0, #10
	bl	fputc
	mov	r3, #0
	str	r3, [fp, #-8]
.L46:
	ldr	r3, [fp, #-12]
	add	r3, r3, #1
	str	r3, [fp, #-12]
.L42:
	ldr	r2, [fp, #-12]
	ldr	r3, [fp, #-28]
	cmp	r2, r3
	bcc	.L47
	ldr	r3, [fp, #-8]
	cmp	r3, #0
	beq	.L48
	ldr	r1, [fp, #-16]
	mov	r0, #10
	bl	fputc
.L48:
	ldr	r3, [fp, #-16]
	mov	r2, #4
	mov	r1, #1
	ldr	r0, .L49+16
	bl	fwrite
	nop
	sub	sp, fp, #4
	@ sp needed
	pop	{fp, pc}
.L50:
	.align	2
.L49:
	.word	.LC9
	.word	.LC10
	.word	.LC11
	.word	.LC12
	.word	.LC13
	.size	print_table, .-print_table
	.section	.rodata
	.align	2
.LC14:
	.ascii	"Usage: %s <modulus> <size> <psi>\012\000"
	.align	2
.LC15:
	.ascii	"Invalid modulus %s: must be at least 2\012\000"
	.align	2
.LC16:
	.ascii	"The modulus is too large: max = %u\012\000"
	.align	2
.LC17:
	.ascii	"Extracted k = %u, not between 1 and q-1\012\000"
	.align	2
.LC18:
	.ascii	"Invalid size %s: must be at least 2\012\000"
	.align	2
.LC19:
	.ascii	"The size is too large: max = %u\012\000"
	.align	2
.LC20:
	.ascii	"psi must be between 2 and %u\012\000"
	.align	2
.LC21:
	.ascii	"invalid psi: %u is not an n-th root of -1  (%u^n = "
	.ascii	"%u)\012\000"
	.align	2
.LC22:
	.ascii	"power(phi, n, q) == 1\000"
	.align	2
.LC23:
	.ascii	"invalid psi: psi^2 is not a primitive n-th root of "
	.ascii	"unity (psi^2 = %u)\012\000"
	.align	2
.LC24:
	.ascii	"             (psi^2)^u = 1\012\000"
	.align	2
.LC25:
	.ascii	"invalid parameters: n = %u is not invertible modulo"
	.ascii	" %u\012\000"
	.align	2
.LC26:
	.ascii	"invalid parameters: k = %u is not invertible modulo"
	.ascii	" %u\012\000"
	.align	2
.LC27:
	.ascii	"Parameters\012\000"
	.align	2
.LC28:
	.ascii	"q = %u\012\000"
	.align	2
.LC29:
	.ascii	"k = %u\012\000"
	.align	2
.LC30:
	.ascii	"n = %u\012\000"
	.align	2
.LC31:
	.ascii	"psi = %u\012\000"
	.align	2
.LC32:
	.ascii	"psi^2 = %u\012\000"
	.align	2
.LC33:
	.ascii	"n^(-1) = %u\012\000"
	.align	2
.LC34:
	.ascii	"k^(-1) = %u\012\000"
	.align	2
.LC35:
	.ascii	"failed to allocate table of size %u\012\000"
	.align	2
.LC36:
	.ascii	"shoup_red_ntt\000"
	.align	2
.LC37:
	.ascii	"shoup_sred_ntt\000"
	.align	2
.LC38:
	.word	__stack_chk_guard
	.text
	.align	2
	.global	main
	.syntax unified
	.arm
	.fpu softvfp
	.type	main, %function
main:
	@ args = 0, pretend = 0, frame = 56
	@ frame_needed = 1, uses_anonymous_args = 0
	push	{fp, lr}
	add	fp, sp, #4
	sub	sp, sp, #64
	str	r0, [fp, #-56]
	str	r1, [fp, #-60]
	ldr	r3, .L71
	ldr	r3, [r3]
	str	r3, [fp, #-8]
	mov	r3,#0
	ldr	r3, [fp, #-56]
	cmp	r3, #4
	beq	.L52
	ldr	r3, .L71+4
	ldr	r0, [r3]
	ldr	r3, [fp, #-60]
	ldr	r3, [r3]
	mov	r2, r3
	ldr	r1, .L71+8
	bl	fprintf
	mov	r0, #1
	bl	exit
.L52:
	ldr	r3, [fp, #-60]
	add	r3, r3, #4
	ldr	r3, [r3]
	mov	r0, r3
	bl	atol
	str	r0, [fp, #-36]
	ldr	r3, [fp, #-36]
	cmp	r3, #1
	bgt	.L53
	ldr	r3, .L71+4
	ldr	r0, [r3]
	ldr	r3, [fp, #-60]
	add	r3, r3, #4
	ldr	r3, [r3]
	mov	r2, r3
	ldr	r1, .L71+12
	bl	fprintf
	mov	r0, #1
	bl	exit
.L53:
	ldr	r3, [fp, #-36]
	ldr	r2, .L71+16
	cmp	r3, r2
	ble	.L54
	ldr	r3, .L71+4
	ldr	r3, [r3]
	ldr	r2, .L71+20
	ldr	r1, .L71+24
	mov	r0, r3
	bl	fprintf
	mov	r0, #1
	bl	exit
.L54:
	ldr	r3, [fp, #-36]
	str	r3, [fp, #-32]
	ldr	r0, [fp, #-32]
	bl	find_k
	str	r0, [fp, #-28]
	ldr	r3, [fp, #-28]
	cmp	r3, #0
	beq	.L55
	ldr	r2, [fp, #-28]
	ldr	r3, [fp, #-32]
	cmp	r2, r3
	bcc	.L56
.L55:
	ldr	r3, .L71+4
	ldr	r3, [r3]
	ldr	r2, [fp, #-28]
	ldr	r1, .L71+28
	mov	r0, r3
	bl	fprintf
	mov	r0, #1
	bl	exit
.L56:
	ldr	r3, [fp, #-60]
	add	r3, r3, #8
	ldr	r3, [r3]
	mov	r0, r3
	bl	atol
	str	r0, [fp, #-36]
	ldr	r3, [fp, #-36]
	cmp	r3, #1
	bgt	.L57
	ldr	r3, .L71+4
	ldr	r0, [r3]
	ldr	r3, [fp, #-60]
	add	r3, r3, #8
	ldr	r3, [r3]
	mov	r2, r3
	ldr	r1, .L71+32
	bl	fprintf
	mov	r0, #1
	bl	exit
.L57:
	ldr	r3, [fp, #-36]
	ldr	r2, .L71+36
	cmp	r3, r2
	blt	.L58
	ldr	r3, .L71+4
	ldr	r3, [r3]
	ldr	r2, .L71+36
	ldr	r1, .L71+40
	mov	r0, r3
	bl	fprintf
	mov	r0, #1
	bl	exit
.L58:
	ldr	r3, [fp, #-36]
	str	r3, [fp, #-24]
	ldr	r3, [fp, #-60]
	add	r3, r3, #12
	ldr	r3, [r3]
	mov	r0, r3
	bl	atol
	str	r0, [fp, #-36]
	ldr	r3, [fp, #-36]
	cmp	r3, #1
	ble	.L59
	ldr	r3, [fp, #-36]
	ldr	r2, [fp, #-32]
	cmp	r2, r3
	bhi	.L60
.L59:
	ldr	r3, .L71+4
	ldr	r0, [r3]
	ldr	r3, [fp, #-32]
	sub	r3, r3, #1
	mov	r2, r3
	ldr	r1, .L71+44
	bl	fprintf
	mov	r0, #1
	bl	exit
.L60:
	ldr	r3, [fp, #-36]
	str	r3, [fp, #-20]
	ldr	r3, [fp, #-20]
	mov	r2, r3
	mul	r2, r3, r2
	mov	r3, r2
	ldr	r1, [fp, #-32]
	mov	r0, r3
	bl	__aeabi_uidivmod
	mov	r3, r1
	str	r3, [fp, #-16]
	ldr	r2, [fp, #-32]
	ldr	r1, [fp, #-24]
	ldr	r0, [fp, #-20]
	bl	power
	str	r0, [fp, #-40]
	ldr	r3, [fp, #-32]
	sub	r3, r3, #1
	ldr	r2, [fp, #-40]
	cmp	r2, r3
	beq	.L61
	ldr	r3, .L71+4
	ldr	r0, [r3]
	ldr	r3, [fp, #-40]
	str	r3, [sp]
	ldr	r3, [fp, #-20]
	ldr	r2, [fp, #-20]
	ldr	r1, .L71+48
	bl	fprintf
	mov	r0, #1
	bl	exit
.L61:
	ldr	r2, [fp, #-32]
	ldr	r1, [fp, #-24]
	ldr	r0, [fp, #-16]
	bl	power
	mov	r3, r0
	cmp	r3, #1
	beq	.L62
	ldr	r3, .L71+52
	mov	r2, #206
	ldr	r1, .L71+56
	ldr	r0, .L71+60
	bl	__assert_fail
.L62:
	mov	r3, #1
	str	r3, [fp, #-40]
	b	.L63
.L65:
	ldr	r2, [fp, #-32]
	ldr	r1, [fp, #-40]
	ldr	r0, [fp, #-20]
	bl	power
	mov	r3, r0
	cmp	r3, #1
	bne	.L64
	ldr	r3, .L71+4
	ldr	r3, [r3]
	ldr	r2, [fp, #-16]
	ldr	r1, .L71+64
	mov	r0, r3
	bl	fprintf
	ldr	r3, .L71+4
	ldr	r3, [r3]
	mov	r2, #27
	mov	r1, #1
	ldr	r0, .L71+68
	bl	fwrite
	mov	r0, #1
	bl	exit
.L64:
	ldr	r3, [fp, #-40]
	add	r3, r3, #1
	str	r3, [fp, #-40]
.L63:
	ldr	r2, [fp, #-40]
	ldr	r3, [fp, #-24]
	cmp	r2, r3
	bcc	.L65
	sub	r3, fp, #48
	mov	r2, r3
	ldr	r1, [fp, #-32]
	ldr	r0, [fp, #-24]
	bl	inverse
	mov	r3, r0
	eor	r3, r3, #1
	and	r3, r3, #255
	cmp	r3, #0
	beq	.L66
	ldr	r3, .L71+4
	ldr	r0, [r3]
	ldr	r3, [fp, #-32]
	ldr	r2, [fp, #-24]
	ldr	r1, .L71+72
	bl	fprintf
	mov	r0, #1
	bl	exit
.L66:
	sub	r3, fp, #44
	mov	r2, r3
	ldr	r1, [fp, #-32]
	ldr	r0, [fp, #-28]
	bl	inverse
	mov	r3, r0
	eor	r3, r3, #1
	and	r3, r3, #255
	cmp	r3, #0
	beq	.L67
	ldr	r3, .L71+4
	ldr	r0, [r3]
	ldr	r3, [fp, #-32]
	ldr	r2, [fp, #-24]
	ldr	r1, .L71+76
	bl	fprintf
	mov	r0, #1
	bl	exit
.L67:
	ldr	r3, .L71+4
	ldr	r3, [r3]
	mov	r2, #11
	mov	r1, #1
	ldr	r0, .L71+80
	bl	fwrite
	ldr	r3, .L71+4
	ldr	r3, [r3]
	ldr	r2, [fp, #-32]
	ldr	r1, .L71+84
	mov	r0, r3
	bl	fprintf
	ldr	r3, .L71+4
	ldr	r3, [r3]
	ldr	r2, [fp, #-28]
	ldr	r1, .L71+88
	mov	r0, r3
	bl	fprintf
	ldr	r3, .L71+4
	ldr	r3, [r3]
	ldr	r2, [fp, #-24]
	ldr	r1, .L71+92
	mov	r0, r3
	bl	fprintf
	ldr	r3, .L71+4
	ldr	r3, [r3]
	ldr	r2, [fp, #-20]
	ldr	r1, .L71+96
	mov	r0, r3
	bl	fprintf
	ldr	r3, .L71+4
	ldr	r3, [r3]
	ldr	r2, [fp, #-16]
	ldr	r1, .L71+100
	mov	r0, r3
	bl	fprintf
	ldr	r3, .L71+4
	ldr	r3, [r3]
	ldr	r2, [fp, #-48]
	ldr	r1, .L71+104
	mov	r0, r3
	bl	fprintf
	ldr	r3, .L71+4
	ldr	r3, [r3]
	ldr	r2, [fp, #-44]
	ldr	r1, .L71+108
	mov	r0, r3
	bl	fprintf
	ldr	r3, [fp, #-24]
	lsl	r3, r3, #2
	mov	r0, r3
	bl	malloc
	mov	r3, r0
	str	r3, [fp, #-12]
	ldr	r3, [fp, #-12]
	cmp	r3, #0
	bne	.L68
	ldr	r3, .L71+4
	ldr	r3, [r3]
	ldr	r2, [fp, #-24]
	ldr	r1, .L71+112
	mov	r0, r3
	bl	fprintf
	mov	r0, #1
	bl	exit
.L68:
	ldr	r3, [fp, #-44]
	str	r3, [sp]
	ldr	r3, [fp, #-16]
	ldr	r2, [fp, #-32]
	ldr	r1, [fp, #-24]
	ldr	r0, [fp, #-12]
	bl	build_shoup_red_table
	ldr	r3, .L71+116
	ldr	r0, [r3]
	mov	r3, #0
	str	r3, [sp, #4]
	ldr	r3, [fp, #-32]
	str	r3, [sp]
	ldr	r3, [fp, #-24]
	ldr	r2, [fp, #-12]
	ldr	r1, .L71+120
	bl	print_table
	ldr	r3, .L71+116
	ldr	r0, [r3]
	mov	r3, #1
	str	r3, [sp, #4]
	ldr	r3, [fp, #-32]
	str	r3, [sp]
	ldr	r3, [fp, #-24]
	ldr	r2, [fp, #-12]
	ldr	r1, .L71+124
	bl	print_table
	ldr	r0, [fp, #-12]
	bl	free
	mov	r3, #0
	ldr	r2, .L71
	ldr	r1, [r2]
	ldr	r2, [fp, #-8]
	eors	r1, r2, r1
	mov	r2, #0
	beq	.L70
	bl	__stack_chk_fail
.L70:
	mov	r0, r3
	sub	sp, fp, #4
	@ sp needed
	pop	{fp, pc}
.L72:
	.align	2
.L71:
	.word	.LC38
	.word	stderr
	.word	.LC14
	.word	.LC15
	.word	65534
	.word	65535
	.word	.LC16
	.word	.LC17
	.word	.LC18
	.word	100000
	.word	.LC19
	.word	.LC20
	.word	.LC21
	.word	__PRETTY_FUNCTION__.5264
	.word	.LC0
	.word	.LC22
	.word	.LC23
	.word	.LC24
	.word	.LC25
	.word	.LC26
	.word	.LC27
	.word	.LC28
	.word	.LC29
	.word	.LC30
	.word	.LC31
	.word	.LC32
	.word	.LC33
	.word	.LC34
	.word	.LC35
	.word	stdout
	.word	.LC36
	.word	.LC37
	.size	main, .-main
	.section	.rodata
	.align	2
	.type	__PRETTY_FUNCTION__.5185, %object
	.size	__PRETTY_FUNCTION__.5185, 6
__PRETTY_FUNCTION__.5185:
	.ascii	"power\000"
	.align	2
	.type	__PRETTY_FUNCTION__.5202, %object
	.size	__PRETTY_FUNCTION__.5202, 8
__PRETTY_FUNCTION__.5202:
	.ascii	"inverse\000"
	.align	2
	.type	__PRETTY_FUNCTION__.5225, %object
	.size	__PRETTY_FUNCTION__.5225, 22
__PRETTY_FUNCTION__.5225:
	.ascii	"build_shoup_red_table\000"
	.align	2
	.type	__PRETTY_FUNCTION__.5236, %object
	.size	__PRETTY_FUNCTION__.5236, 6
__PRETTY_FUNCTION__.5236:
	.ascii	"shift\000"
	.align	2
	.type	__PRETTY_FUNCTION__.5264, %object
	.size	__PRETTY_FUNCTION__.5264, 5
__PRETTY_FUNCTION__.5264:
	.ascii	"main\000"
	.ident	"GCC: (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0"
	.section	.note.GNU-stack,"",%progbits
