mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2018-09-11, 20:42   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

11×23 Posts
Default order of a function =/= p-1

A peaceful night for all persons,


i am looking for an algebraic structure which has not an order as p-1 or p+1

What about

(r 1)(x) = f(x,y) mod p where r is element N and p prime.
(0 r )(y)

Would be nice to get a short link about this topic.


Greetings from the algebraic structures,

there seems to be more than expected
Bernhard

Last fiddled with by bhelmes on 2018-09-11 at 20:43
bhelmes is offline   Reply With Quote
Old 2018-09-12, 15:22   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×5×293 Posts
Default

I'm so confused by this question.

You're looking for an algebraic structure A, that is, a set S and a collection O1, O2, O3, ..., On of operators on S. You then want A to have an order other than p-1 or p+1, but what do you mean by "order" and what is p?

It sounds like p is some fixed prime number and your set is {0, 1, ..., p-1}, with your operations being some "natural" operation or operations mod p. If your operations are unary, each element of S has an order; perhaps you mean the exponent of the group so induced. Since this divides the order of the group, that is, p, it can't be equal p+1 and can equal p-1 only if p = 2. Otherwise, please clarify what you mean.
CRGreathouse is offline   Reply With Quote
Old 2018-09-12, 18:10   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

C9716 Posts
Default

I too was confused. I think Bernhard means f(x,y) = [1,r;0,1]*[x,y]~ in pari-speak. HTH.
paulunderwood is online now   Reply With Quote
Old 2018-09-12, 20:11   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10110111001002 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I too was confused. I think Bernhard means f(x,y) = [1,r;0,1]*[x,y]~ in pari-speak. HTH.
In which case f(x, y) is the column vector [x + r*y; y], where r is (apparently) some fixed but unspecified natural number.
CRGreathouse is offline   Reply With Quote
Old 2018-09-12, 20:22   #5
bhelmes
 
bhelmes's Avatar
 
Mar 2016

11·23 Posts
Default

A peaceful and pleasant night for everyone,


if i have a function f(x) mod p, where p is a prime and x is element 0 ... p-1
and the function should have as result a natural number from 0 to p-1
then there will be a cycle of function terms.


f(x) : Np -> Np



The amount of results of f(x) is limited, therefore if i make a recursion,
there has to be a repetition of f(x).


i take an x0, calculate x1=f(x0) mod p, calculate x2=f(x1) mod p and so on



I thought that the expression "order" describes the huge of the cylic structure.


For example, you could take a 2x2-matrix A and a vector (x,y)
and consider the function f(x,y)=A(x,y) mod p
where the mod p is taken for every x and y


The question was,

if A=[r,1;r,0] so that the eigenwert is r, what will be the huge of the cyclic
structure ?



I will try to improve my mathematical english, but it is not easy for me
to explain an idea and translate it exactly in another language.


Greetings from the recursive functions

Bernhard
bhelmes is offline   Reply With Quote
Old 2018-09-13, 16:23   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×5×293 Posts
Default

I don't see a useful way of answering that in general, it depends on the value of p, r, and the starting values of the column vector. For p = 2, r = 0 you get order 1. For p = 2, r = 1 you get 1 if you start with [2;2] and 3 otherwise, which I will denote
[3 3]
[3 1].

For p = 3, r = 0 you get order 1; for p = 3, r = 1 you get
[8 8 8]
[8 8 8]
[8 8 1];
for p = 3, r = 2 you get
[3 1 3]
[1 3 3]
[3 3 1].

For p = 5, r = 0 you get order 1; for p = 5, r = 1 you get
[20 4 20 20 20]
[20 20 20 4 20]
[ 4 20 20 20 20]
[20 20 4 20 20]
[20 20 20 20 1];
for p = 5, r = 2 you get
[24 24 24 24 24]
[24 24 24 24 24]
[24 24 24 24 24]
[24 24 24 24 24]
[24 24 24 24 1];
for p = 5, r = 3 you get
[4 4 1 4 4]
[1 4 4 4 4]
[4 4 4 1 4]
[4 1 4 4 4]
[4 4 4 4 1];
for p = 5, r = 4 you get
[3 3 3 3 3]
[3 3 3 3 3]
[3 3 3 3 3]
[3 3 3 3 3]
[3 3 3 3 1].

Code for generating these:
Code:
findCycle(ff:closure,startAt,flag=0)={
	my(power=1,len=1,tortoise=startAt,hare=ff(startAt),mu);
	while (tortoise != hare,
		if (power == len,
			tortoise = hare;
			power <<= 1;
			len = 0
		);
		hare = ff(hare);
		len++
	);

	tortoise=hare=startAt;
	for (i=1,len,
		hare = ff(hare)
	);
	while(tortoise != hare,
		tortoise=ff(tortoise);
		hare=ff(hare);
		mu++
	);
	if(flag, print("mu = "mu));
	len
};
addhelp(findCycle, "findCycle(ff, startAt): Finds the length of the first cycle that startAt, ff(startAt), ff(ff(startAt)), ... enters into. Prints the prefix length (steps taken before the cycle begins).");

f(p,r,startAt)=my(A=[r,1;r,0]);findCycle(v->A*v%p,startAt);
g(p,r)=matrix(p,p,x,y,f(p,r,[x;y]));
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ECM curve group order Brain Miscellaneous Math 1 2010-12-08 01:00
Number of groups for given order Raman Puzzles 6 2010-09-05 17:43
Constructing numbers that have S-smooth order CRGreathouse Math 7 2009-10-22 18:36
Forum order? Xyzzy Forum Feedback 5 2007-01-28 10:35
A property about the order of divisors of (Mq-1)/2 T.Rex Math 3 2005-11-14 18:23

All times are UTC. The time now is 01:32.

Sat Jun 6 01:32:51 UTC 2020 up 72 days, 23:05, 1 user, load averages: 1.23, 1.22, 1.26

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.